对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;
}

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

墙上根本没有更多的啤酒瓶.

但是怎么恢复打印:

将一个瓶子放入回收处,在垃圾箱中放入一个空瓶子.

将一个瓶子放入回收处,在垃圾箱中放入2个空瓶子.

将一个瓶子放入回收箱中,在垃圾箱中放入3个空瓶子.

将一个瓶子放入回收箱中,将4个空瓶放入垃圾箱.

if函数已经打印出一条消息,但是不是终止它也会转到else.这怎么可能？如何在"numberOfBottles"中从1增加到4？

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

Answer 1

3瓶:

SingSong(3):
 PRINT 2 LINES
 SingSong(2):
     PRINT 2 LINES
     SingSong(1):
          PRINT 2 LINES
          SingSong(0):
               PRINT 1 LINES
          PRINT RECYCLE LINE
     PRINT RECYCLE LINE
 PRINT RECYCLE LINE

在最后的内部递归调用发生后,它会通过每个方法调用退出并调用回收消息.

Answer 2

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

首先,让我们检查一个替代程序,该程序与程序基本相同,使用非递归函数调用.

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;
}

我希望很明显,每个函数都会打印几行,调用下一个函数,然后打印另一行.每个被调用的函数依次执行此操作,例如,SingSongFor4()打印2行,然后SingSongFor3调用.这将打印其2行,然后调用SingSongFor2(),打印其行等等.SingSongFor1()不调用任何其他函数,因此它打印所有三行然后返回SingSongFor2()完成,依此类推链.总之,X bottles on the wall/take one down当您按下函数调用"向下"时,您将获得8行,然后在向上"向上"反向时,将4行"放入垃圾箱中".

你的功能没有任何不同,除了它已被参数化并添加一点逻辑以确定它应该如何行动SingSongFor1()以及何时它应该像其他3一样.我说它没有什么不同,除了在你的情况下你有一个副本每次调用程序时共享的程序文本,而不是文本的4个单独(几乎相同)的副本.共享文本副本的原因是每个函数调用的本地上下文 - 参数,变量以及有关程序所在位置和程序执行状态的一些内务处理信息.

通常,此上下文信息包含在称为堆栈的特殊数据结构中.它被称为堆栈,因为您将一个堆叠在另一个之上,然后从"顶部"一次一个地移除它们.每个堆栈帧包含一个函数调用的上下文:参数 - 在您的情况下numberOfBottles; 局部变量 - oneFewer; 以及有关函数结束或返回时应执行哪个语句的信息.当调用函数时,对应于该调用的帧被压入堆栈并执行函数的文本.完成后,弹出框架,并在调用函数停止的位置继续执行(为此目的,它存储在弹出的堆栈框架中).它恢复使用堆栈的新"顶部"框架为它的上下文.

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

Answer 3

递归函数调用是堆叠的.所以它是这样的:

SingSongFor(4)
  |
  v
SingSongFor(3)
  |
  v
SingSongFor(2)
  |
  v
SingSongFor(1)
  |
  v
SingSongFor(0)

最后一次调用打印出没有更多瓶子然后返回,这就是魔术发生:它返回上一次调用,然后打印有关回收站的消息,并返回上一次再次打印其消息的调用, 等等.