C++的递归向后返回

Question

这是代码:

#include <iostream>
using namespace std;
void countdown(int n);

int main(){
    countdown(4); // call the recursive function
    return 0;
}

void countdown(int n){
    cout << n << endl;

    if (n > 0){
        countdown(n-1); // function calls itself
    }

    cout << n << endl; // intended part of code
}

简单运行:

4
3
2
1
0
0
1
2
3
4

问题:为什么这个递归函数从0重新计数到4并且不在0处停止？

Answer 1

因为递归函数调用存储在堆栈中.因此,当一个函数调用返回时,它会从堆栈中弹出,然后执行函数调用的下一行.

void countdown(int n){
cout << n << endl; // This line calls 4 3 2 1 0

if (n > 0){
countdown(n-1); // function calls itself
}

cout << n << endl;; //This line print 0 1 2 3 4
}

假设代码行之前的数字是行号:

 1   void countdown(int n){
 2   cout << n << endl; // This line calls 4 3 2 1 0

 3   if (n > 0){
 4    countdown(n-1); // function calls itself
 5   }

  6  cout << n << endl;; //This line print 0 1 2 3 4
  7  }

Suppose countdown is called with n = 2,
Then, Your stack will initially contain function call with n = 2.
Because of line 2, 2 gets printed. 
Because of line 4, function with n = 1 gets called. So, now stack has 1|2
Now because of line 2 again, 1 gets printed. 
Because of line 4, function with n = 0 gets called. So Now stack is 0|1|2
Line 2 prints 0.
Line 3 condition fails and so line 4 is not executed. 
Line 6 prints 0. 
Line 7 tells that function execution is over and hence it will pop out of stack. Now stack is 1|2.
Now, function with n = 1 resumes its operation from line 5. 
So, line 6 makes it print 1.
line 7 tells that function execution is over and hence it will pop out of stack. Now stack is 2. 
So, function with n =2 resumes its operation from line 5.
line 6 makes it print 2.
line 7 tells function execution is over and hence it will pop out of stack. And now it will return to main.