对C中的递归感到困惑

Question

我有以下代码:

#include <stdio.h>

void SingSongFor(int numberOfBottles){

    if (numberOfBottles == 0){
        printf("There are simply no more bottles of beer on the wall.\n\n");
    } else {
        
        printf("%d bottles of beer on the wall. %d bottles of beer.\n", numberOfBottles, numberOfBottles);
        
        int oneFewer = numberOfBottles - 1;
        printf("Take one down, pass it around, %d bottles of beer on the wall.\n\n", oneFewer);
        
        SingSongFor(oneFewer); // This function calls itself!
        
        // Print a message just before the function ends
        printf("Put a bottle in the recycling, %d empty bottles in the bin.\n",numberOfBottles);
    }
}

int main(int argc, const char * argv[]) {
  
    // We could sing 99 verses, but 4 is easier to think about
    SingSongFor(4);
    
    return 0;
}

根据我的理解，程序必须在打印后终止:

There are simply no more bottles of beer on the wall.

但是怎么恢复打印了:

Put a bottle in the recycling, 1 empty bottles in the bin.

Put a bottle in the recycling, 2 empty bottles in the bin.

Put a bottle in the recycling, 3 empty bottles in the bin.

Put a bottle in the recycling, 4 empty bottles in the bin.

if 函数已经打印出一条消息，但它并没有终止它，而是到达了 else。这怎么可能？ “numberOfBottles”如何从 1 增加到 4？

更新:这是我对代码的理解。如果我错了，请纠正我。

Answer 1

要了解您的程序为何如此运行，有必要了解函数调用的工作原理。它是递归的这一事实可能使编译器能够进行一些优化以提高程序的效率，但从概念上讲递归并不会真正改变正在发生的事情。

首先，让我们检查一个与您的程序基本相同的替代程序，使用非递归函数调用。

void SingSongFor4(){

        printf("4 bottles of beer on the wall. 4 bottles of beer.\n");

        printf("Take one down, pass it around, 3 bottles of beer on the wall.\n\n");

        SingSongFor3();

        // Print a message just before the function ends
        printf("Put a bottle in the recycling, 4 empty bottles in the bin.\n");
    }
}

void SingSongFor3(){

        printf("3 bottles of beer on the wall. 3 bottles of beer.\n");

        printf("Take one down, pass it around, 2 bottles of beer on the wall.\n\n");

        SingSongFor2();

        // Print a message just before the function ends
        printf("Put a bottle in the recycling, 3 empty bottles in the bin.\n");
    }
}

void SingSongFor2(){

        printf("2 bottles of beer on the wall. 2 bottles of beer.\n");

        printf("Take one down, pass it around, 1 bottles of beer on the wall.\n\n");

        SingSongFor1();

        // Print a message just before the function ends
        printf("Put a bottle in the recycling, 2 empty bottles in the bin.\n");
    }
}

void SingSongFor1(){

        printf("1 bottles of beer on the wall. 1 bottles of beer.\n");

        printf("Take one down, pass it around, 0 bottles of beer on the wall.\n\n");


        printf("Put a bottle in the recycling, 1 empty bottles in the bin.\n");
    }
}

int main(int argc, const char * argv[]) {

    // We could sing 99 verses, but 4 is easier to think about
    SingSongFor4();

    return 0;
}

我希望每个函数打印几行，调用下一个函数，然后打印另一行是显而易见的。每个被调用的函数依次执行此操作，例如，打印 2 行 SingSongFor4()，然后调用 SingSongFor3。这会打印它的 2 行，然后调用 SingSongFor2()，它会打印它的行等等。 SingSongFor1() 不调用任何其他函数，因此它打印所有三行，然后返回到 SingSongFor2() 完成，依此类推链。总而言之，当您按照“向下”函数调用时，您会得到 8 行 X bottles on the wall/take one down，然后当您返回时得到 4 行“Put a bottle in the bin” “向上”相反的方向。

你的函数没有任何不同，除了它被参数化并添加了一些逻辑来确定它什么时候应该像 SingSongFor1() 一样以及什么时候应该像其他 3 个一样。我说它没有什么不同，只是在你的情况下，你有一个程序文本的单个副本，该副本由程序的每次调用共享，而不是 4 个单独的(几乎相同的)文本副本。使共享文本副本成为可能的是每个函数调用的本地上下文 - 参数、变量和一些关于程序所在位置和程序执行状态的内部管理信息。

通常，此上下文信息包含在称为堆栈的特殊数据结构中。之所以称为堆叠，是因为您将东西一件一件地堆叠起来，然后从“顶部”开始一次将它们一件一件地移除。每个堆栈帧都包含一次函数调用的上下文:参数 - 在您的情况下为 numberOfBottles；局部变量 - oneFewer；以及有关函数结束或返回时应执行哪个语句的信息。当一个函数被调用时，与该调用对应的帧被压入堆栈并执行函数的文本。当它完成时，框架被弹出，并在调用函数中从它停止的地方恢复执行(为此目的，它被存储在弹出的堆栈框架中)。它继续使用堆栈的新“顶部”框架作为其上下文。

不过，重要的是您的递归函数的工作方式与任何其他函数完全相同 - 每次调用它时都会获得一个属于自己的新上下文，即使函数的文本是相同的。它执行到完成，然后返回到先前的上下文 - 这可能是相同的函数，但具有不同的上下文。