What is Recursion

For Complete YouTube Video: Click Here

In this class, we will try to understand What is Recursion.

We have already discussed examples of algorithm analysis in our previous classes.

What is Recursion

So far, we have covered many examples of algorithm analysis on iterative methods.

As part of writing the programs using iteration, we have another technique of writing programs using recursion.

Recursion is a programming technique in which a function calls itself.

To understand this, we will consider the algorithm shown below.

Above is an algorithm to find the factorial of a given number.

Without using iteration, we can find the factorial using recursion.

Before understanding how recursive algorithms can find factorial, we will discuss the process.

The image below is what a process looks.

Process means a program in execution.

For example, consider the above factorial program.

The process represents how the program is executed on RAM.

The program’s machine code is stored in the program part of the process.

Above the program, we have multiple sections of memory to store the variables, dynamic memory allocations, functions and other functionalities in the program.

The static and global variables of the program will be stored as shown in the diagram.

The dynamic memory allocations in the program will be stored in the corresponding section, as shown in the diagram.

The stack in the diagram is used whenever a function call is made.

Let’s consider the factorial algorithm.

The stack part of the process is essential to understanding how recursion works.

For example, assume that the “main function” made a factorial(4) function call.

As we have discussed, for every function call, a new element in a stack will be created.

This new row of the stack is called an activation record.

The activation record will have the local variables of the function and the instruction pointer.

The instruction pointer defines the line of code where the function call was made.

For factorial(4), a new activation record gets created with the local variable n = 4 and instruction pointer 4.

The instruction pointer is line four because executing the factorial(4) function call gets transferred to the factorial(3) function call.

For factorial(3) function call, a new activation will gat created.

Similarly, a new activation record gets created for factorial(2).

When factorial(1) gets called, the return one will get executed, which is the program’s base code.

The base code is for the termination of recursion. Without base code, the algorithm will fall into an infinite loop.

After returning one it will return the values to all the called functions and final output of 24 will be returened.

For very clear understanding of the concepts click the Youtube link provided on the top.