Definition:
Recursion is a technique in which a function calls itself directly or indirectly.
Directly means it will call itself. Indirectly means, it will call a function that will call itself recursively.
Let’s understand recursion with help of example:
Below is the program to find number of times a recursion function is called.
#include<iostream>
using namespace std;
int fun(int n)
{
if (n == 1)
return 1; // base case
else
return 1 + fun(n-1);
}
int main()
{
int n = 5;
cout<< "The number of times the function are "<<fun(5)<<endl;
return 0;
}
In the above program, the function “fun()” is a recursive function. “main()” is calling recursive function indirectly. Then the function “fun()” will call itself directly.
For writing any recursive function, there should be a base case. Base case is used to exit out of the recursion loop. If base case is not there, it will result in stack overflow and will crash the program.
Hence for every recursion program there should be a base case.
Recursion and Stack Frame:
From the above program we shall understand how stack frame gets effected when using recursion function.
So we called the function with n = 3 value. We know that, in C, local c variables are stored in stack. When you call a function, it’s activation record along with unction parameters are also stored.
So from main() function we call fun() function.
Stack Frame:
Changes in the fun() function:
int fun(3 )
{
if (n == 1)
return 1; // base case
else
return 1 + fun(2);
}
As we are calling fun (2), we transfer the control from fun (3) to fun (2) as shown above.
Now int fun (2)
Stack Frame:
Changes in the fun() function:
int fun( 2 )
{
if (n == 1)
return 1; // base case
else
return 1 + fun(1);
}
Now we call fun (1) from fun (2). Hence we transfer the control from fun (2) to fun (1).
Stack frame:
Changes in the fun () function.
int fun( 1 )
{
if (n == 1)
return 1; // base case
}
Now in fun (1) now “n == 1” is true, hence we return 1. Which mean, we are returning 1 to the calling function from the stack frame. We can see that the calling function is fun (2).
int fun( 2 )
{
else
return 1 + fun(1);
}
int fun( 2 )
{
else
return 1 + 1; // return 2
}
Hence, 2 will get returned to the calling function of fun (2).
From the stack frame, we can see that fun (3) is calling fun (2). Hence the fun (3) will become:
int fun( 3 )
{
else
return 1 + fun( 2 );
}
int fun( 3 )
{
else
return 1 + 2; // return 3
}
Now the value “3” will be returned to its calling function i.e main function.
On a high level we can summarize the above steps as below:
Recursion Tree:
What is a Recursion Tree?
As we saw in previous section, we saw what a recursion is and how the stack frame changes when a recursive call is made.
A recursion tree is nothing but a visual representation of recursive calls.
Let’s understand the recursion tree by taking an example of printing n^th Fibonacci number.
The pseudo code to find nth Fibonacci number is as below:
fib( n )
{
int n <= 1
return n;
else
return fib ( n -1 ) + fib ( n - 2 )
}
and when we call the fib function with n = 5. The stack framer and Fibonacci tree is as shown below:
Then fib ( 5 ) is a recursive call it will be:
Right now the compiler is executing fib ( 4 ) all the other are in paused state.
Then fib ( 4 ) will make a call to fib ( 3 ), fib ( 3 ) will make a call to fib ( 2 ), fib (2) will call fib ( 1 )… it can be showed as below
Now fib ( 1 ), it will return 1 and also it is popped from stack.
Now fib ( 2 ) is in stack, it will call fib ( 0 ) and fib (0) will be put into stack.
Now fib ( 0 ) will return 0 and as fib ( 2 ) has called fib ( 0 ) and fib ( 1 ) the final value for fib ( 2 ) will be 1, and fib ( 2 ) will be popped out of stack. Now the execution will flow to fib ( 3 ).
Now fib ( 3 ) already called fib ( 2 ) hence it will call fib ( 1 ) and fib ( 1 ) will be placed into the stack.
Again fib ( 1 ) will call fib ( 0 ) and it can be showed as below:
Now for fib ( 4 ), it already called fib ( 3 ), hence it will call fib ( 2 ), again fib ( 2 )will call fib ( 0 ) and fib ( 1 ).
The calculated values can be as below:
Hence fib ( 4 ) value will be “ 2 + 1 = 3”. 3 will be returned to fib ( 5 )
Again fib ( 5 ) will call fib ( 3 ), fib ( 3 ) will call fib ( 2 ), then fib ( 2 ) will call fib ( 1 ). Fib ( 1 ) will return 0.
The final recursion tree will be as below:
This is the basic of recursion and the changes in the stack frame when you call a recursion function.
This is an important topic. Because in the next chapter i.e dynamic programming and backtracking it uses recursion to get the results.
Further Reading:
