Recursion is a process in which a function calls itself again and again. We use recursion to solve bigger problem by dividing it into smaller similar sub-problems and then call them recursively.

## Types of Recursion

### Recursive functions can be classified on the basis of

**a)** Based on functions call itself – Direct / Indirect**b)** Based on pending operation at each recursive call – Tail Recursive/ Head Recursive**c)** Based on the structure of the function calling pattern – Linear / Tree

## Based on functions call Itself

### 1). Direct Recursion

- If a function calls itself from within itself is known as Direct Recursion.
- When the method invokes itself it is direct.

```
int func(int num) {
if (num == 0)
return 1;
else
return func(num - 1);
}
```

Here, function ‘func’ is calling itself. This is an example of direct recursion.

### 2). Indirect Recursion

- In Indirect Recursion, more than one function call one another mutually in a circular manner.
- For example, if a function ‘fun1()’ , calls function ‘fun2()’, which calls function ‘fun3()’ which again leads to ‘fun1()’ being invoked is called indirect recursion.

```
#include <stdio.h>
void fun2(int n);
void fun1(int n)
{
if (n > 0) {
printf("%d ", n);
fun2(n - 1);
}
}
void fun2(int n)
{
if (n > 1) {
printf("%d ", n);
fun1(n - 2);
}
}
int main()
{
fun1(10);
return 0;
}
```

## Based on Pending Operation

### 1). Tail / Bottom Recursion

- Tail Recursion is an example of Direct Recursion, If a recursive function is calling itself and that recursive call is the last statement in the function then it’s known as Tail Recursion.
- We can also say that if no operations are pending when the recursive function returns to its caller.
- It is an efficient method as compared to others, as the stack space required is less and even compute overhead will get reduced.
- After the call, the recursive function performs nothing.

```
#include <stdio.h>
void fun(int n)
{
if (n > 0) {
printf("%d ", n);
fun(n - 1); // Last statement in the function
}
}
int main()
{
fun(5);
return 0;
}
```

**Time Complexity For Tail Recursion:** O(n)**Space Complexity For Tail Recursion: **O(n)

### 2). Head/Top Recursion

- Tail Recursion is an example of Direct Recursion, If a recursive function is calling itself and that recursive call is the first statement in the function then it’s known as Head Recursion.
- Nothing will perform before calling of a recursive function.

```
#include <stdio.h>
void fun(int n)
{
if (n > 0) {
fun(n - 1); // First statement in the function
printf("%d ", n);
}
}
int main()
{
fun(5);
return 0;
}
```

**Time Complexity For Head Recursion:** O(n)**Space Complexity For Head Recursion:** O(n)

## Based on the structure of the function

### 1). Linear Recursion

- A linear recursive function is a function that only makes a single call to itself each time the function runs.
- Our Factorial recursive function is a suitable example of linear recursion as it only involves multiplying the returned values and no further calls to the function.

**Below is an example of Linear Recursion**

```
int factorial(int n)
{
if (n==1)
return 1; //base case, as we know that factorial of 1 is 1
else
return n*factorial(n-1); //recursive case
}
```

### 2). Tree recursion

- In Tree recursion, Instead of a single function call there are two recursive calls for each non-base case.
- Functions with two recursive calls are referred to as binary recursive functions.
- In Tree recursion, there are pending operations that involve another recursive call to the function.

**Below is an example of Tree Recursion**

```
#include <stdio.h>
void fun(int n)
{
if (n > 0) {
printf("%d ", n);
fun(n - 1); //calling first time
fun(n - 2); //calling second time
}
}
int main()
{
fun(10);
return 0;
}
Fibonacci series is also a example of tree/binary recursion
int fibonacci(int i){
if(i==0) return 0;
else if(i==1) return 1;
else return (fibonacci(i-1)+fibonacci(i-2));
}
```

**Time Complexity For Tree Recursion:** O(2^n)**Space Complexity For Tree Recursion:** O(n)

### 3). Nested Recursion

- In Nested recursion, a recursive function will be pass as the parameter in a recursive function itself.
- That means “recursion inside recursion”.

**Example of Nested Recursion**

```
#include <stdio.h>
int fun(int n)
{
if (n > 100)
return n - 10;
// A recursive function is passes as parameter
// in recursive function itself or recursion
// inside the recursion
return fun(fun(n + 11));
}
int main()
{
fun(50);
printf("%d", r);
return 0;
}
```