C语言中的递归混淆

Question

我正在阅读一本关于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如何跟踪瓶数。另外一个问题是，我对这个主题的困惑是否意味着我不能继续学习编程？在这一点上，我已经掌握了很多东西。

- Henry F

---

为什么会有重复？https://dev59.com/jGrWa4cB1Zd3GeqP_HKE - Aniket Inge

不要因为一开始不理解而感到沮丧！如果你刚接触递归，可能会觉得它很难。你可以尝试阅读http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/chapters/05-intro-to-recursion.pdf。 - nullptr

非常感谢 nullptr，这很令人鼓舞！对不起 Aniket，我的搜索中没有找到。 - Henry F

Answer 1

这里是关键所在：

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

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

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

当numberOfBottles变为零的时候，堆栈上有100个嵌套调用singTheSong的副本。最终，该函数在不进行递归的情况下返回，并且所有等待的堆栈副本将依次返回。

- paddy

Answer 2

拿一张纸，为每个调用绘制调用栈，记录参数的值和返回地址（这样你就可以看到它解开了）。这样会更容易跟踪。

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

- alex

Answer 3

第一次调用singTheSong时，numberOfBottles是99。

然后它调用singTheSong(numberOfBottles-1)（99-1=98），这将调用新瓶数为98-1=97的singTheSong(numberOfBottles-1)。

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

- sapi

Answer 4

首先回答你的最后一个问题 - 不，这并不一定意味着你的编程职业生涯注定失败。递归很重要，但它的大部分好处（比如遍历树和图）已经在库中实现了，你不需要深入理解它。当你学习函数式编程时，它将更加关键，但那时你已经对它有很好的掌握。

这表明你不理解函数的本质以及调用堆栈的作用。这是需要学习的，而递归是一个很好的方式。

递归的问题在于会在调用堆栈上产生许多相同函数的调用。在这种情况下，当你从 99 开始时，是的，`oneFewer = 98`。但然后，在完成函数之前，你调用 `singTheSong` 并传入 `oneFewer` 即 98。这会导致调用 `singTheSong` 的 `oneFewer` 值为 97。

这将导致你在调用堆栈上堆叠出 100 个相同函数的实例。在第 100 首歌曲中，你会打印 "There are no bottles left"，然后你的函数退出。然后是 "1 bottle" 的函数已经完成，所以它退出，允许 "2 bottles" 函数完成，以此类推，直到最初的函数完成。

- Scott Mermelstein

---

很好的建议和描述。 - alex

Answer 5

需要翻译的内容如下：

需要理解的是函数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语句和“没有瓶子了”的基本情况。

- stevenstevensteven

---

只是挑剔一下 - 从99到0会给你100个实例。 :-) - Scott Mermelstein

Answer 6

在“拿一个下来，传递它”的陈述之后，

singTheSong(oneFewer);

使用oneFewer进行调用，它是保存特定迭代中瓶子数量值的变量。因此，numberOfBottles最初为99，然后oneFewer被赋值为98。然后，oneFewer = 98传递给singTheSong。这次，被称为numberOfBottles的参数具有与前一个迭代中oneFewer相同的值。在这个迭代中，oneFewer获得了97的值，这个循环继续进行，直到达到基本情况，即oneFewer为0并传递给singTheSong。 singTheSong获取该值，并知道已到达if情况，因此停止。

- starcodex

---

基本上由于递归调用singTheSong(oneFewer);有一个参数oneFewer，因此随着堆栈不断增加，它会将numberOfBottles变量分配给== oneFewer？ - Henry F

那正是这样的情况 :) 如果你理解了这一点，那么你就理解了大部分递归。 - starcodex