Recursion and its Types [with Examples]

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

Introduction to Recursion

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

For example, consider the following function in C++:

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

Here, sum is a recursive function because it is calling itself.

In recursion, the code inside the function gets executed repeatedly until the execution control jumps out of the function scope.

Notice, the function sum 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, the execution control returns back to the calling statement.

This exit condition inside a recursive function is known as base condition.

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

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.

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.

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 an argument of n=5 i.e., tail(5), the output would be:

5 4 3 2 1

All iteration of ‘for’ and ‘while’ loop 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.