如何准确地理解函数递归？ [英] How to understand function recursion precisely?

问题描述

我目前正在编写一些分治算法，其中函数递归在各处使用，但是我不清楚或不知道它到底是如何工作的，这就是为什么我在这里发布它并希望您不要介意它也是基本。

I am currently programming some divide-conquer algorithms, where function recursions are used everywhere, but I have very vague idea or no idea how exactly it works, and that's why I post it here and hope you don't mind it's too basic.

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

For example, if we have the following code:

#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），终端中的打印结果是：

I tested Recursion(3) and the print out in the terminal is:

3
2
1
0
0
1
2
3

我可以理解函数递归调用的概念，但是我不了解机制的运作方式。例如，在他们再次无法调用该函数后会做什么？例如，在这里，我可以理解它从3打印到0，但为什么它又从0打印到3？我听说这是因为函数递归在堆栈中存储了一个递归，当到达底端时它也必须删除。

I can understand the concept of recursive call of the function but I don't understand the mechenism how it works. For example, what will they do after they can't call the function again? For example, here, I can understand it prints from 3 to 0 but why it also prints from 0 to 3 again? I heard it's because function recursion is stored in a stack for one recursion and when it reaches the "bottom" it also has to delete.

但是无论如何，我不会知道这一点。因此，有人可以帮我清楚地告诉我这里发生了什么以及函数调用的确切流程吗？

But anyway, I don't know about it. So, can anyone help me out and clearly tell me what happened here and the exact flow of function call?

感谢您的帮助！

推荐答案

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

The key to understanding recursion is the concept of the call stack. The call stack consists of "frames". A stack frame contains a function's local variables and an invisible return address. The classic physical analogy is a stack of plates. When you make a function call a plate (stack frame) is added to the top of the stack. When you return from a function the top plate (stack frame) is removed. You can only use the plate (stack frame) that is on top.

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

Recursive functions work the same way as ordinary functions. They are a little tricky because you can have multiple instances of their local variables on the stack at a given time. However, like other functions the function only refers to the stack frame that is on the top of the stack.

为说明其工作原理，让我们遍历程序以显示

To illustrate how this works let's walk through your program showing how the call stack grows and shrinks.

让我们从基本情况开始：0。 Recursion（0）;

Let's start with the base case: 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（），堆栈再次为空：stack-> | |<-堆栈顶部

1. Enter main: The stack is empty: Bottom of stack->||<-Top of stack
2. Recursion(0); Enter Recursion the stack has grown: Bottom of stack->|0|<-Top of stack
3. cout << n << endl; The value of n is 0 so the output is "0"
4. if (n > 0). 0 is not greater than 0 so Recursion(-1) is not called.
5. cout << n << endl; The value of n is 0 so the output is "0"
6. Return to main() the stack is empty again: Bottom of stack->||<-Top of stack

输出为

0
0

很简单，没有递归发生。让我们迈出下一步。 Recursion（1）;

Simple enough, no recursion took place. Let's take the next step. 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. 返回到对递归的第一个调用。堆栈底部-> | 1 |<-堆栈顶部


10. cout<< n<< endl; n的值为1，因此输出为 1

1. Enter main: Bottom of stack->||<-The top of stack
2. Recursion(1); Enter Recursion: Bottom of stack->|1|<-Top of stack
3. cout << n << endl; The value of n is 1 so the output is "1"
4. if (n > 0). 1 is greater than 0 so Recursion(0); is called.
5. Enter Recursion: Bottom of stack->|1,0|<-Top of stack
6. cout << n << endl; The value of n in this stack frame is 0 so the output is "0"
7. if (n > 0). 0 is not greater than 0 so the function does not recurse.
8. cout << n << endl; The value of n is 0 so the output is "0"
9. Return to the first call to Recursion. Bottom of stack->|1|<-Top of stack
10. cout << n << endl; The value of n is 1 so the output is "1"

输出

1
0
0
1

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

Let's go through the execution one final time with n == 2

1. 输入main：Bottom-> ||< -Top


2. Recursion（2）; 输入递归：Bottom-> | 2 | <-顶部


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 |<-顶部


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（）。底部-> ||<-顶部

1. Enter main: Bottom->||<-Top
2. Recursion(2); Enter Recursion: Bottom->|2|<-Top
3. cout << n << endl; "2"
4. if (n > 0). 2 is greater than 0 so Recursion(1); is called.
5. Enter Recursion: Bottom->|2,1|<-Top
6. cout << n << endl; "1"
7. if (n > 0). 1 is greater than 0 so Recursion(0); is called.
8. Enter Recursion: Bottom->|2,1,0|<-Top
9. cout << n << endl; "0"
10. if (n > 0). 0 is not greater than 0 so the function does not recurse again.
11. cout << n << endl; "0"
12. Return. Bottom->|2,1|<-Top
13. cout << n << endl; "1"
14. Return. Bottom->|2|<-Top
15. cout << n << endl; "2"
16. Return to main(). Bottom->||<-Top

输出

2
1
0
0
1
2

这篇关于如何准确地理解函数递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！