How to understand function recursion precisely?

Question

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!

Answer 1

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

Answer 2

You are right, I also find recursive functions difficult to understand. Here is what i do, if i see a recursive function: run all the code step by step in your mind. This advice may seem trivial, but most of the time it works for me. Let's look at your code: You call Recursion() function with parameter 3. It prints n and n>0 that's why it calls Recursion(2) (note that we didn't return from the Recursion(3) call we are still in it and now we are also in Recursion(2). The same is for recursion(1) and 0. Now n>0 conditional is false. It prints 0. and we return from recursion(0) We print 1 and return from recursion(1) and it goes on the recursion(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)