理解递归代码的遍历

Question

如果我的手在我们遍历的每一行代码上，那么当我们点击一个函数调用时，我的手会转到被调用的函数并且该函数开始执行，然后我的手 returns 回到调用函数的那一行。

现在说到递归，当我一直调用同一个函数时，手的行为如何？每个函数调用都有新手吗？我不明白代码如何"goes back up a tree of recursive calls"。我知道有一个堆栈。我看过所有解释它的视频

我不明白的是，如果我写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

将调用堆栈想象成一盘索引卡。堆栈开始时是空的。你唯一能做的就是写下一张新的索引卡并将其放在最上面，或者把最上面的东西拿掉。

到运行时间，那个托盘里有一些东西放在那里，但现在让我们假装当 main() 开始到运行时托盘是空的。

假设每个函数都是一本书中的一个章节。每个页面都有一堆单独的句子，每个句子告诉你做一件特定的事情。其中之一可能是 "go to another chapter and do what it says, using this information I have here." 当你遇到这样的句子时，你需要记住如何回到原来的位置，所以你在索引卡上写下以下内容：

您当前在哪一章以及您刚刚阅读了该章的哪一句（例如，可能是页码、段落编号和该段落中的句子编号）。
您在被要求转到另一章之前使用的任何信息。

你把这张卡片放在托盘的最上面，然后翻到另一章开始做事。

当你读到一个写着 "you are done with this chapter, go back to the last chapter with this result" 的句子时，你就把卡片从上面拿下来，翻到上面写的任何一章，找到紧跟卡片指示的句子，然后继续从那里开始。

这就是这里发生的一切。章节是函数。句子是机器指令。你带到另一章的东西是函数参数。您从章节中取回的东西是 return 值。您在索引卡上记下的 "stuff you were working with" 是函数调用时任何函数局部变量的值。

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

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

所以在你的情况下，是的，你可以认为你有 "multiple hands." 无论你递归到同一个函数有多深，你都必须在每次递归调用时重新开始 returns.

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

理解递归代码的遍历

Comprehending the walk through of a recursive code

c++

recursion

recursive-backtracking