-5

我对 C 编程语言中的递归有疑问。

我正在读一本关于 c 的书，我得到了这段我不太明白的代码

第一个问题：

void singTheSong(int numberOfBottles)
{
  if (numberOfBottles == 0)
  {
    printf("There are simply no more bottles of beer on the wall.\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",
           oneFewer);

    singTheSong(oneFewer); // This function calls itself!

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

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

  return 0;
}

所以这应该是一首歌。我理解 if 部分

printf("Put a bottle in the recycling, %d empty bottles in the bin.\n",
numberOfBottles);

我不明白如何从 0 增加到 98

第二个问题：

为什么不一直到99？它停在98。

请用简单的英语解释，因为我不使用英语作为主要语言（有些困难）

谢谢

4

3 回答 3

3

在考虑递归时，考虑调用堆栈发生了什么是有帮助的。

在这种情况下，重要的是要注意

  printf("Put a bottle in the recycling, %d empty bottles in the bin.\n",
       numberOfBottles);

紧接着：

 singTheSong(oneFewer);

所以之前的一切都singTheSong()被执行了，然后递归调用发生了添加一个新的堆栈帧。numberOfBottles在达到 0 瓶 之前不会发生回收打印语句。

当numberOfBottles命中 0 时，代码会一一倒退，尽管所有这些堆栈帧。每个框架都有自己的numberOfBottles. 所以它从堆栈顶部开始倒带 1，然后到达该函数调用的末尾，弹出堆栈帧，然后移动到下一帧，numberOfBottles即 2，然后是 3，......一直倒带背部。

这展示了递归的风险之一——想想它使用了多少内存。并不是说递归本质上是不好的。在某些情况下，如果使用得当（例如用于教授调用堆栈如何工作），它可能会很好。

于 2013-10-18T23:09:43.247 回答
2

理解这样的递归程序的最佳方法是假装你是计算机并手动按照说明进行操作。使用一张纸来跟踪程序中的变量。由于函数中有两个变量，所以写在纸上：

numberOfBottles
oneFewer

每次递归调用函数时，在右侧创建一个新列作为当前值，并在返回时划掉这些值。因此，当您第一次致电时singTheSong，您将拥有：

numberOfBottles 99
oneFewer

（oneFewer开始时为空）。你说墙上有 99 瓶啤酒。99瓶啤酒。然后你分配oneFewer，所以现在你有：

numberOfBottles 99
oneFewer        98

然后你说拿下来，传过来，墙上有 98 瓶啤酒。然后你进行递归调用singTheSong(oneFewer)，当你重新输入函数时，你有：

numberOfBottles 99 98
oneFewer        98

您重复上述所有步骤。如果你继续这样做，最终你会遇到最后一种情况：

numberOfBottles 99 98 97 ... 3 2 1 0
oneFewer        98 97 96 ... 2 1 0

这一次，(numberOfBottles == 0)函数开头的测试会成功。而不是按照我们之前所有的步骤，它只会说墙上没有更多的啤酒瓶。并返回。

正如我上面所说，当您返回时，您将变量表中的列划掉。

numberOfBottles 99 98 97 ... 3 2 1
oneFewer        98 97 96 ... 2 1 0

然后你在它调用之后返回到函数的步骤singTheSong(oneFewer)，它说把一个瓶子放在回收站里，1 个空瓶子放在垃圾箱里。然后该函数再次返回，因此您划掉最后一列：

numberOfBottles 99 98 97 ... 3 2
oneFewer        98 97 96 ... 2 1

并说将一个瓶子放入回收站，将 2 个空瓶子放入垃圾箱。当您从每个递归调用中不断返回时，您将返回到每个保存的值numberOfBottles，因此它会计数。最终你会回到第一列：

numberOfBottles 99
oneFewer        98

你会说把一个瓶子放在回收站里，99 个空瓶子放在垃圾桶里。这一次当你返回时，你会回到原来的main()函数，你就完成了。

于 2013-10-18T23:16:00.293 回答
0

“它从 0 增加到 98”，因为您仅在单步执行所有递归（该函数在此行之前调用自身）时才执行这部分代码，现在您正在展开所有递归。

第二：注意你的堆栈，不要使用递归！

制造

于 2013-10-18T23:12:02.617 回答