5

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

例如，如果我们有以下代码：

#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？我听说这是因为函数递归存储在堆栈中进行一次递归，当它到达“底部”时，它也必须删除。

但无论如何，我对此一无所知。那么，任何人都可以帮助我并清楚地告诉我这里发生了什么以及函数调用的确切流程吗？

谢谢你的帮助！

4

4 回答 4

6

你是对的，我也觉得递归函数很难理解。如果我看到一个递归函数，这就是我要做的：在你的脑海中逐步运行所有代码。这个建议可能看起来微不足道，但大多数时候它对我有用。让我们看看您的代码：您使用参数 3 调用 Recursion() 函数。它打印 n 和 n>0 这就是它调用 Recursion(2) 的原因（请注意，我们没有从 Recursion(3) 调用中返回，我们仍在它现在我们也在 Recursion(2) 中。对于 recursion(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)
于 2013-07-27T22:43:13.230 回答
6

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

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

为了说明它是如何工作的，让我们通过你的程序来展示调用堆栈是如何增长和缩小的。

让我们从基本情况开始：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. 输入主：底部->||<-顶部
  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. 返回主（）。底部->||<-顶部

输出

2
1
0
0
1
2
于 2013-07-28T01:32:06.010 回答
4

调用自身的函数与调用另一个函数的函数没有什么不同：在继续之前，它必须等待它调用的函数返回。

顺便说一句，递归可能看起来很优雅，但总的来说它不是最有效的编程方式：例如，它使内联函数变得不可能，因此保证了上下文切换的开销。总有一种更有效的方法来获得递归函数的相同结果。但是对于某些问题，递归实现更直观，并且不会以任何明显的方式变慢。您在评论中给出的示例合并排序是一个很好的示例。

关于这个的一些有趣的讨论：
从递归到迭代的方法
每个递归都可以转换成迭代吗？

我的最后建议：当问题不需要这种方法时，不要使用递归，例如在计算阶乘时。

于 2013-07-27T22:42:23.560 回答
3

有时从基本情况开始更容易理解递归，即不递归的情况。在您的示例中，当 n<=0 时，无需更多呼叫即可解决呼叫。让我们从那个开始。

如果调用 Recursion(0)，预期的结果是两次打印零，一次在 if 之前，一次在 if 之后。if 里面的代码不执行。

现在，Recursion(1) 第一次打印值 1，然后调用 Recursion(0)，它又像以前一样打印 0 两次，然后执行返回到 Recursion(1)，在 Recursion 执行之后再次打印 1 (0)。这就是为什么你会看到 1 0 0 1。这同样适用于 Recursion(2)，它将 Recursion(1) 的结果包裹在两个周围。

于 2013-07-27T22:54:37.920 回答