**Summary:** In this tutorial, we will learn what is recursion in C++ and the types of recursion in C++ with examples.

## Introduction to Recursion in C++

Recursion is a process in which a function calls itself either directly or indirectly. In recursion the corresponding function is known as a recursive function.

When a function calls itself, the code inside the function gets executed again.

1 2 3 4 | int sum(int n){ /* Statements*/ return n+ sum(n-1); // Function calling itself } |

Here, `sum`

is a recursive function.

Notice, the function repeats itself endlessly and doesn’t have any stopping point.

To stop the successive recursive call, we put a condition inside the function. If that particular condition is satisfied or true, we exit out of the function.

This exit condition in a recursive function is known as **base condition**.

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

In the above example, `n==1`

is the base condition and s`um(n-1)`

is recursive call.

The sum function when initially called with an argument value of 5 i.e. `sum(5)`

, the recursive process execution will look like this:

The above function calls are executed in **stack** fashion i.e. traced back to complete the function operation (LIFO).

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

`5 4 3 2 1`

All loop’s iteration can be converted into recursion.

But, Recursion is twice slower than iteration because it has to backtrack the past recursive calls.

In this tutorial, we learned what is recursion in C++ and the two types of recursion i.e. head and tail recursion with examples.