c++ - 如何准确理解函数递归？

Question

我目前正在编写一些分而治之的算法，其中到处都使用函数递归，但我的想法非常模糊或者不知道它到底是如何工作的，这就是我将它发布在这里的原因，希望你不要介意它太基本。

例如，如果我们有如下代码:

#include<iostream>
using namespace std;
void Recursion(int n)
{
  cout << n << endl;
  if(n > 0)
  {
    Recursion(n-1);
  }
  cout<<n<<endl;
}

int main()
{
  Recursion(3);
  return 0;
}

我测试了 Recursion(3)，终端中的打印输出是:

3
2
1
0
0
1
2
3

我能理解函数递归调用的概念，但我不明白它的工作原理。例如，他们无法再次调用该函数后，他们会做什么？例如，在这里，我可以理解它从 3 打印到 0，但为什么它又从 0 打印到 3？我听说这是因为函数递归存储在一个堆栈中进行一次递归，当它到达“底部”时它也必须删除。

但无论如何，我不知道这件事。那么，谁能帮我清楚地告诉我这里发生了什么以及函数调用的确切流程？

感谢您的帮助!

Answer 1

理解递归的关键是调用栈的概念。调用堆栈由“帧”组成。堆栈帧包含函数的局部变量和不可见的返回地址。经典的物理类比是一堆盘子。当您进行函数调用时，一个板(堆栈框架)将添加到堆栈的顶部。当您从函数返回时，顶板(堆栈框架)将被移除。您只能使用顶部的板(堆栈框架)。

递归函数的工作方式与普通函数相同。它们有点棘手，因为您可以在给定时间在堆栈上拥有它们局部变量的多个实例。但是，与其他函数一样，该函数仅引用位于堆栈顶部的堆栈帧。

为了说明这是如何工作的，让我们浏览一下您的程序，展示调用堆栈是如何增长和收缩的。

让我们从基本情况开始:0。Recursion(0);

1. 进入main:栈为空:栈底->||<-栈顶
2. Recursion(0);输入递归堆栈已增长:堆栈底部->|0|<-堆栈顶部
3. cout << n << endl; n的值为0所以输出为“0”
4. if (n > 0) . 0 不大于 0，因此不调用 Recursion(-1)。
5. cout << n << endl; n的值为0所以输出为“0”
6. 返回 main() 栈再次为空:栈底->||<-栈顶

输出将是

0
0

很简单，没有发生递归。让我们进行下一步。 Recursion(1);

1. 输入main:栈底->||<-栈顶
2. Recursion(1);输入递归:栈底->|1|<-栈顶
3. cout << n << endl; n的值为1所以输出为"1"
4. if (n > 0) . 1 大于 0 所以 Recursion(0);被称为。
5. 输入递归:栈底->|1,0|<-栈顶
6. cout << n << endl;此堆栈帧中 n 的值为 0，因此输出为“0”
7. if (n > 0) . 0 不大于 0，因此函数不递归。
8. cout << n << endl; n的值为0所以输出为“0”
9. 返回对 Recursion 的第一次调用。栈底->|1|<-栈顶
10. cout << n << endl; n的值为1所以输出为"1"

输出

1
0
0
1

让我们最后一次执行 n == 2

1. 输入main: Bottom->||<-Top
2. Recursion(2);输入递归:Bottom->|2|<-Top
3. cout << n << endl; “2”
4. if (n > 0) . 2 大于 0 所以 Recursion(1);被称为。
5. 输入递归:Bottom->|2,1|<-Top
6. cout << n << endl; “1”
7. if (n > 0) . 1 大于 0 所以 Recursion(0);被称为。
8. 输入递归:Bottom->|2,1,0|<-Top
9. cout << n << endl; “0”
10. if (n > 0) . 0 不大于 0，因此函数不会再次递归。
11. cout << n << endl; “0”
12. 返回。底部->|2,1|<-顶部
13. cout << n << endl; “1”
14. 返回。底部->|2|<-顶部
15. cout << n << endl; “2”
16. 返回 main()。底部->||<-顶部

输出

2
1
0
0
1
2