問題描述

我目前正在編寫一些分治算法，其中到處都使用函數(shù)遞歸，但我有非常模糊的想法或不知道它究竟是如何工作的，這就是我將其發(fā)布在這里的原因，希望您不要介意基本的.

例如，如果我們有以下代碼:

#include使用命名空間標準；無效遞歸(int n){cout<<＜＜結束;如果(n > 0){遞歸(n-1)；}cout<<n<<endl;}int main(){遞歸(3)；返回0；}

我測試了 Recursion(3)，在終端打印出來的是:

32100123

我能理解函數(shù)遞歸調用的概念，但我不理解它是如何工作的機制.比如，不能再次調用該函數(shù)后，他們會怎么做?例如，在這里，我可以理解它從 3 打印到 0 但為什么它又從 0 打印到 3?我聽說是因為函數(shù)遞歸是為了一次遞歸存儲在一個堆棧中，當它到達底部"時，它也必須刪除.

但無論如何，我不知道.那么，誰能幫我清楚地告訴我這里發(fā)生了什么以及函數(shù)調用的確切流程?

感謝您的幫助！

理解遞歸的關鍵是調用棧的概念.調用堆棧由幀"組成.堆棧幀包含函數(shù)的局部變量和不可見的返回地址.經典的物理類比是一堆盤子.當您進行函數(shù)調用時，會在堆棧頂部添加一個板(堆棧框架).當您從函數(shù)返回時，頂板(堆棧框架)被移除.您只能使用位于頂部的板(堆疊框架).

遞歸函數(shù)的工作方式與普通函數(shù)相同.它們有點棘手，因為您可以在給定時間在堆棧上有多個局部變量的實例.但是，和其他函數(shù)一樣，該函數(shù)只引用棧頂?shù)臈?

為了說明這是如何工作的，讓我們通過您的程序來展示調用堆棧如何增長和收縮.

讓我們從基本情況開始: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

輸出為

很簡單，沒有發(fā)生遞歸.讓我們進行下一步.遞歸(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，因此函數(shù)不會遞歸.
8. cout <<＜＜endl; n 的值為 0 所以輸出為0"
9. 回到對遞歸的第一次調用.棧底->|1|<-棧頂
10. cout <<＜＜endl; n 的值為 1 所以輸出為1"

輸出

1001

讓我們用 n == 2 執(zhí)行最后一次

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，因此函數(shù)不會再次遞歸.
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

這篇關于如何準確理解函數(shù)遞歸?的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！