如何准确理解函数递归?

2021-12-16 00:00:00 递归 c++

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

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

#include使用命名空间标准；无效递归(int n){cout<<＜＜结束;如果(n > 0){递归(n-1)；}cout<<n<<endl;}int main(){递归(3)；返回0；}

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

32100123

我能理解函数递归调用的概念，但我不理解它是如何工作的机制.比如，不能再次调用该函数后，他们会怎么做?例如，在这里，我可以理解它从 3 打印到 0 但为什么它又从 0 打印到 3?我听说是因为函数递归是为了一次递归存储在一个堆栈中，当它到达底部"时，它也必须删除.

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

感谢您的帮助！

解决方案

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

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

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

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

  1. 进入main:栈为空:栈底->||<-栈顶
  2. Recursion(0); Enter Recursion the stack has成长:Bottom of stack->|0|<-Top of stack
  3. cout <<＜＜endl; n 的值为 0 所以输出为0"
  4. if (n > 0).0 不大于 0，因此不会调用 Recursion(-1).
  5. cout <<＜＜endl; n 的值为 0 所以输出为0"
  6. 返回main()，栈再次为空:Bottom of stack->||<-Top of stack

输出为

<预><代码>00

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

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

输出

1001

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

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

输出

210012

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;
}

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

3
2
1
0
0
1
2
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?

Thanks for your help!

解决方案

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.

Let's start with the base case: 0. Recursion(0);

  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

The output would be

0
0

Simple enough, no recursion took place. Let's take the next step. Recursion(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"

Output

1
0
0
1

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

  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

Output

2
1
0
0
1
2

相关文章