c++ - 理解递归代码的演练

Question

如果在执行过程中将手放在每一行代码上，那么当我们敲函数调用时，我的手会转到被调用的函数，并且该函数开始执行，之后，我的手将返回到函数被调用。现在谈到递归时，当我继续调用相同的函数时，手的行为如何？每个函数调用都有新手吗？我不明白代码如何“返回一棵递归调用树”。我了解这里有堆栈。我看过所有解释它的视频。我不明白的是，如果我在递归调用中写上一个cout语句，然后在递归调用下写一个cout语句，那么我理解为什么递归调用上的cout语句执行的次数与递归函数的调用次数相同，但是如何执行呢？递归调用下面的cout语句也会被执行多次？
这是一个例子

int Factorial(int n)
{
  cout<<"first cout statement before the recursive call";
  if( n == 0 )
     return 1;
  int F = n*Factorial(n-1);
  cout<<"second cout statement after the recursive call";
  return F; 
}
int main()
{
 int n;
 cin>>n;
 int result = Factorial(n);
 cout<<result;
}

这是下面的输出。

first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call
first cout statement before the recursive call

second cout statement after the recursive call  //Notice these
second cout statement after the recursive call
second cout statement after the recursive call
second cout statement after the recursive call
second cout statement after the recursive call
120

Answer 1

可以将 call 堆栈想像成索引卡托盘。堆栈开始为空。您唯一可以做的就是写下一张新的索引卡，放在最上面，或者取出最上面的东西。

在运行时该托盘中放有一些东西，但目前，让我们假设main()开始运行时该托盘为空。

假设每个功能都是一本书中的一章。每个页面都有一堆单独的句子，每个句子都告诉您要做一件事。这些事情之一可能是“使用我在这里的信息，转到另一章，按照它所说的去做”。遇到这样的句子时，您需要记住如何回到原来的状态，因此在索引卡上写下以下内容:

您当前所在的章节以及您刚刚阅读该章节的句子(例如，页面编号，段落编号和该段落中的句子编号)。

在被要求转到另一章之前，您正在使用的任何信息。

您将此卡放在托盘的顶部，然后转到另一章开始做事情。

当您说出“您已完成本章，返回到此结果的最后一章”的句子时，您将插卡从顶部移开，翻回其所指的章节，在卡指示一张，然后从那里继续。

这就是这里正在发生的一切。章节是功能。句子是机器指令。进入另一章的内容是函数参数。从章节中获取的东西是返回值。放在索引卡上的“正在使用的东西”是在进行函数调用时所有函数局部变量的值。

当您进行递归调用时，您仍然将某些东西放在堆栈上，但是只是转到了已经读过的同一章，只是信息略有不同。当您需要离开本章时，最上面的卡片可能会说您仍在同一章中，但是句子不同，信息也不同。

您有一系列的嵌套调用，每个递归调用一个堆栈帧。当控制权从递归调用中退出时，您仍在相同的函数中，但是具有与调用前相同的局部变量值。

因此，就您的情况而言，是的，您可能会想到您拥有“多手”。无论您递归到同一个函数的深度如何，都必须在每次递归调用返回时进行备份。

老实说，递归调用和非递归调用在程序流逻辑上进行的方式上没有任何区别(在尾调用优化的情况下除外)。编译器和机器代码并不关心调用相同的函数，而是以两种方式执行相同的过程。