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:

### 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:

### 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:

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**.