Recursion
First up all we will se what those the word “Recursion” means. Recursion is one of the important application of Stacks. Recursion is something when a function call itself again and again. Let’s see a basic code view of recursive program to understand how its works.
In the above example if N ≤ 0 the program return the value and ends there itself but till the condition is not satisfied the else function run again and again these is known as recursion.
Let’s see how the things are worked in background of a recursive code.
Our Operating System make an use of Stack to handle function call. Whenever we call a function an activation record are created on a stack. Now, you all wonder what is an “Activation Record”. Activation Record is a stack frame. The Auto variable and all parameter are consits or part of activation record. In Activation Record there are Return Value address. Let’s see example of Activation Record and Return value address.
The Expression which is not executed its address is save in activation records. Let’s see example of recursive code and how value are stored in activation record.
Let’s see how above code works. How Activation Record is created. We are taking n = 4 in the example.
In the above code n = 4 else block is executed. So, first statement return the value 4 + F(3), second returns 3 + f(2) and so on. The final value of function is
f(1) = 1, f(2) = 3, f(3) = 6 and f(4) = 10.
These is the process how recursion works and value are stored in activation records.
Now, we will see what is an “Recursion Tree”. We use Recursion Tree when we have only print statement in our code. Let understand it with an example.
To get the output of the above code with the help of recursion tree we have to perform Depth First Search from Left to Right. Let’s take an small value of n to see how recursion tree forms. Let’s take n = 3.
That’s all for these blog hope you all like it. Thanks for reading and for your precious time to read the blog.