## What is Recursion?

When a **function calls itself then it is called Recursion**. Recursion in c++ is a programming property and is implemented through function.

When a function calls itself it becomes a loop and hence it will never end. At the beginning of the function, there is a condition. **which is called base condition**. This condition if is true then the further calling of the function will be stopped.

1 2 3 4 5 |
int sum(int n){ if(n==1) //Base Condition return 1; return n+ sum(n-1); // Funtion calling itself } |

In the above example, *n==1* is the base condition and *sum(n-1)* is calling itself i.e recursion. So when sum function is called initially with an argument value of 5 i.e *sum(5)* then the recursive process will look like this:

The above function call is stored in the stack and traced back to complete the function operation. The Stack is maintained by Operating System, So there is no need to create and manage stack explicitly.

## Types of Recursion

Recursion can be of two types:

- Head Recursion
- Tail Recursion

### Head Recursion

In Head Recursion, the main body of the function comes after the recursive call statement i.e function calls itself at the beginning of the function.

1 2 3 4 5 6 |
void head(int n){ if(n==0) return; head(n-1); //Function calling itself cout << n; //main operation of this function i.e body } |

In the above function, the function is calling itself before printing. Therefore if* head(5)* is called, the output will be:

1 |
1 2 3 4 5 |

### Tail Recursion

In tail recursion, the function calls itself at the end of the function. Hence all main task of the function is done beforehand.

1 2 3 4 5 6 |
void tail(int n){ if(n==0) return; cout << n; //main operation of this function i.e body tail(n-1); //Function calling itself } |

If the above function is called with value 5 i.e *tail(5)*. Then the output will be:

1 |
5 4 3 2 1 |

All iteration can be converted into recursion. But Recursion is twice slower than iteration because it has to go down to all recursive call and again backtrack using the stack.

That’s all for the recursion in C++. If you have any doubt then comment below.