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.

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.

In the above example, n==1 is the base condition and sum(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:

Recursion in C++

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:

  1. Head Recursion
  2. 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.

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.

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.

Leave a Reply