What is Recursion? | Concepts of Recursion – Brain Mentors Skip to content

What is Recursion? | Concepts of Recursion

The process in which a function calls itself is called recursion. Recursion is a method where the solution of a problem depends upon the solutions that are small instances of the same problem. 

The diagram shows how recursion works: 

Why we need recursion?

Any problem can be solved by a recursive method as well as by the iterative method. But whenever we have a problem that is complex to do just by iterative/looping method. Then we are going to divide the problem into a smaller instance of the same problem that means we solve it by the recursive method.

Recursion vs Iteration

Recursion
Iteration
Function calls itself.
A set of instructions repeatedly executed.
For functions
For loops
Infinite recursion can lead to system crash/stack overflow.
Whereas, infinite iteration consumes CPU cycles.
The time complexity of recursion can be found by finding the value of the nth recursive call in terms of the previous calls.
The time complexity of iteration can be found by finding the number of cycles being repeated inside the loop.

What is call Stack?

A call stack is a stack data structure that is used to trace the sequence of the function call. When a function called then it’s get pushed inside the stack and when a function returns it popped out from the stack.

Three Concepts of Recursion

  • Base Case (Terminating Case)
  • Small Problem 
  • Processing Logic

Let’s take an example to understand it:

CODE :
OUTPUT:

STACK REPRESENTATION:

image22

Types of Recursion:

Tail Recursion:

If a recursive function is calling itself and that recursive call is the last statement in the function. After that call there is nothing, it is not performing anything.

Let’s take an example to understand it:

CODE:
OUTPUT:

Head Recursion:

If a recursive function is calling itself and that recursive call is the first statement in the function and some operations are performed after the call. The function doesn’t have a processor to perform any operation at the time of calling. It has to do everything at the time of returning.

Let’s take an example to understand it:

CODE:
OUTPUT:

Linear Recursion:

A linear recursive function is a function that only makes a single call to itself each time the function runs. It has something to process before and after the call.

Let’s take an example to understand it:

CODE:
OUTPUT:

Tree Recursion:

If a function is a recursive function that is calling itself more than one time.

Let’s take an example to understand it:

CODE:
OUTPUT:

Indirect Recursion:

There may be more than one function and they are calling one another in a circular fashion.

Let’s take an example to understand it:

CODE:
OUTPUT:

Nested Recursion:

A recursive function call will pass the parameter as a recursive call. It is called nested recursion.

Let’s take an example to understand it:

CODE:
OUTPUT:

Stack Building

Stack building is used to print the sequence in reverse order. In the below given example, the method stack_building first print the value and then apply recursive call. So it is called a stack building.

CODE: Print 5 4 3 2 1 using recursion.
OUTPUT:

STACK REPRESENTATION:

image3 (1)

Stack Falling

Stack falling is just like a normal recursion and it is recursively called the function till then the base case is false. Once the base case is true then it can print the sequence as given in the below example.

CODE: Print 1 2 3 4 5 using recursion and condition is that you have to start by taking value = 5.
OUTPUT:

STACK REPRESENTATION:

image3 (2)

That’s all for now. Hope you have learned something through my Blog. I will see you in the next Data Structures and Algorithms blog. If you are interested in Data Structures and Algorithms, then you also opt for our exclusive Brain Mentor’s Data Structures and Algorithms Online Course.



Sign Up and Start Learning