3

我正在阅读一本书，其中有一章涉及 C 中的递归。它将 99 瓶歌曲打印到日志中。这是代码：

void singTheSong (int numberOfBottles) {

    if (numberOfBottles == 0) {
        printf("There are no more bottles left.\n");
    } else {
        printf("%d bottles of bear 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", oneFewer);

        singTheSong(oneFewer); 
    }
}

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

    singTheSong(99);
    return 0;
}

输出就像歌曲的演唱方式一样。我难以理解的是，numberOfBottles变量如何改变其值？我看到它在oneFewer变量中减去了一个，但我无法理解它是如何工作的。在我看来，日志上写着“墙上有 99 瓶熊，99 瓶啤酒。拿下一个，传过来，墙上有 98 瓶啤酒。” 重复，从未低于 98。我不确定numberOfBottles价值是如何改变的，因此如何oneFewer跟踪瓶子的数量。还有一个问题，我对这个话题的困惑是否是继续编程的坏兆头？我已经把它钉牢了，直到这一点。

4

6 回答 6

8

关键在这里：

    int oneFewer = numberOfBottles - 1;
    singTheSong(oneFewer);

生成一个新的调用singTheSong，其中numberOfBottles是 98 而不是 99。该函数获取值为 98 的本地副本numberOfBottles。

Stack                                  numberOfBottles
------------------------------------------------------
singTheSong                            99
  singTheSong                          98
    singTheSong                        97
      singTheSong                      96
        ...                            ...
          singTheSong                  1
            singTheSong                0

到numberOfBottles零时，有 100 个嵌套调用singTheSong坐在堆栈上。最后，函数不进行递归就返回，堆栈中等待的所有副本将一次返回一个。

于 2013-05-20T01:01:40.240 回答
2

拿一张纸，绘制每次调用的调用堆栈，记录参数的值和返回地址（这样你就可以看到它unwind）。它应该更容易遵循。

执行将始终进入else块，除了最后一个（基本情况），它将进入if块。这将意味着该数字将递减，直到达到0.

于 2013-05-20T00:57:52.053 回答
2

第一次singTheSong被称为，numberOfBottles是99。

然后它调用singTheSong(numberOfBottles-1)( 99 - 1 = 98)，然后调用新的瓶数singTheSong(numberOfBottles-1)，即。98 - 1 = 97

重复该过程，直到达到基本情况。

于 2013-05-20T00:58:53.647 回答
2

首先回答你的最后一个问题 - 不，这并不一定意味着你的编程生涯注定要失败。递归对于理解很重要，但它的大部分良好功能用途（行走树和图表跳到脑海中）已经在您不需要深入理解它的库中实现。当你开始使用函数式编程时，它会更重要，但到那时，你就会很好地掌握它。

它表明您不了解的是函数的性质以及调用堆栈的作用。这对学习很重要，递归是一种很好的方法。

递归的问题在于它会导致调用堆栈上同一函数的多次调用。在这种情况下，当你从 99 开始时，是的，oneFewer= 98。但是，在你完成函数之前，你调用singTheSong传入 oneFewer，即 98。这将调用singTheSong值为oneFewer97。

这将导致您有 100 个相同函数的实例全部堆叠在调用堆栈上。在第 100 首歌曲中，您打印“There are no bottle left”，然后您的函数退出。然后“1瓶”的函数已经完成，所以它退出，让“2瓶”函数完成，依此类推，直到你的调用堆栈完成，直到原始函数完成。

于 2013-05-20T01:04:12.050 回答
2

要理解的是函数 singTheSong 正在调用自己。所以函数 main 调用 singTheSong(99)。该函数打印出一些东西，然后将 99 - 1 粘贴到变量 oneFewer 中，然后以 oneFewer 的值再次调用 singTheSong。所以这一次，它传递的值不是 99，而是 98。

新函数是 singTheSong 的不同实例。它对之前调用的 singTheSong 一无所知。它只知道它的值是 98，它应该打印一些东西，将 98-1 粘贴到 oneFewer 中，然后再次调用 singTheSong。

到程序降到 0 时，实际上将有 99 个 singTheSong 实例。但是当它被零调用时，它不会再次递归，而是打印“没有瓶子剩下”。然后程序通过所有 99 个案例返回并最终结束。因此 0 是基本情况，并且每个递归算法都有一个可以达到的基本情况是至关重要的。

如果您想进一步了解这一点，请尝试输入 printf("%d %d \n",oneFewer, numberOfBottles); 在递归调用之后。

如果您想使计算机崩溃（并查看该站点的名称），请尝试删除 if 语句和“没有瓶子剩下”的基本情况。

于 2013-05-20T01:07:44.607 回答
1

在“取下一个，传递它”声明之后，

singTheSong(oneFewer);

使用 oneFewer 调用，它是保存该特定迭代中瓶子数量值的变量。所以 numberOfBottles 一开始是 99，然后将 oneFewer 分配给 98。然后，将 oneFewer = 98 传递给 singTheSong。这一次，被称为numberOfBottles的参数与前一次迭代中的 oneFewer 具有相同的值。在这个迭代中，oneFewer 获得了 97 的值，并且这个循环一直持续到达到基本情况，也就是 oneFewer 为 0 并被传递给 singTheSong。singTheSong 采用该值并知道它已达到if情况，因此它停止。

于 2013-05-20T01:04:12.763 回答