如何准确理解函数递归？

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

你说得对，我也觉得递归函数很难理解。这就是我所做的，如果我看到一个递归函数：在你的脑海中一步一步地运行所有代码。这个建议可能看起来微不足道，但大多数时候它对我有用。让我们看看你的代码：你用参数 3 调用 Recursion() 函数。它打印 n 和 n>0 这就是它调用 Recursion(2) 的原因（注意我们没有从 Recursion(3) 调用返回，我们仍在它现在我们也在递归（2）中。对于递归（1）和0也是如此。现在n>0条件是假的。它打印0。我们从递归（0）返回我们打印1并从递归返回(1) 然后继续递归 (3)

Recursion(3)
    Recursion(2)
        Recursion(1)
            Recursion(0)  
            return from Recursion(0)
        return from Recursion(1)
    return from Recursion(2)
return from Recursion(3)

Answer 2

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

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

为了说明这是如何工作的,让我们通过您的程序来展示调用堆栈如何增长和缩小.

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

1. 输入main:堆栈为空:stack-> || <-Top of stack的底部
2. Recursion(0); 输入堆栈增长的递归:堆栈的底部 - > | 0 | <堆栈的顶部
3. cout << n << endl; n的值为0,因此输出为"0"
4. if (n > 0).0不大于0因此不调用递归(-1).
5. cout << n << endl; n的值为0,因此输出为"0"
6. 返回main()堆栈再次为空:stack-> || <-Top of stack的底部

输出将是

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