**Recursion** is a powerful tool for writing algorithms supported in some programming languages like **C**, **C++**. Recursion is a process in which a function calls itself and it is applicable to problems where something can be defined in terms of itself. Recursion technique is used to solve simple to highly challenging problems. Let’s walk through some simple examples to understand the concept of recursion and how it is implemented in C++ language. Same fundamentals are applicable for any other language which supports recursion.

**Computing Factorial of a Number**

**Factorial** computation is a classic example where a recursive algorithm can be applied.

Factorial of a number **n** is represented as n!.

Mathematically, factorial(n) or n! = n * n-1 * n-2 * … * 2 * 1

For e.g. 5! = 5 * 4 * 3 * 2 * 1 = 120

Similarly, 4! = 4 * 3 * 2 * 1 = 24

Can we express **5!** in terms of **4!** ? Yes, we can.

5! = 5 * 4! = 5 * 24 = 120

In General, n! = n * (n-1)!

Thus, factorial computation is a perfect case where a function can be defined or expressed in terms of itself.

Suppose, **factorial( n )** is a function which computes n!. Then, **factorial( n ) = n * factorial( n – 1 )**

It is very important to identify the **boundary case** while implementing the recursive algorithm so that we can return from a recursive function. In this case, boundary case is when **n = 0** i.e **0! = 1**.

Following program implements the recursive algorithm to compute factorial :

#include<iostream> using namespace std; /* recursive function to compute factorial of 'n' * recursion formula :- factorial(n) = n * factorial(n-1) */ int factorial(int n) { if ( n == 0 ) { // boundary case return 1; } else { // apply recursive formula int fact = n * factorial(n-1); return fact; } } int main() { int n = 5; int res = factorial(n); cout << "Factorial of " << n << " is " << res << endl; return 0; }

**Finding n ^{th} term of Fibonacci Series**

In a

**fibonacci series**, every term is equal to the sum of previous two terms. Consider the series below :

**0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , ……**

Suppose,

**fib( n )**denotes the

**n**term of fibonacci series.

^{th}So, in the above series,

**fib ( 6 ) = 8**

Observe that

**fib ( 6 ) = fib ( 5 ) + fib ( 4 ) = 5 + 3 = 8**

In general, we can deduce the recursive formula for computing the

**n**term as

^{th}**fib( n ) = fib( n – 1 ) + fib( n – 2 )**

Boundary Case :

**fib( 0 ) = 0**and

**fib( 1 ) = 1**

Following program implements the recursive algorithm to compute

**n**term of fibonacci series :

^{th}#include<iostream> using namespace std; /* Recursive algorithm to compute nth term of fibonacci series * Recursive Formula : fib(n) = fib(n-1) + fib(n-2) */ int fib(int n) { if ( n == 0 || n == 1) { // boundary case ( 0th term = 0 and 1st term = 1 ) return n; } else { // apply generic recursive formula int n_term = fib(n-1) + fib(n-2); return n_term; } } int main() { int n = 6; int n_term = fib(n); cout << "Term " << n << " of fibonacci series is " << n_term << endl; return 0; }

**Role of System Stack in Recursive Algorithms**

Whenever, a function **f1( )** makes a call to another function **f2( )**, information about the current state of **f1( )** is stored in the system stack so that when control returns from **f2( )**, we can resume operations in **f1( )**. Same concept is applicable to recursive algorithms. When a function **func( )** makes a call to itself, the information about the current call instance is saved in system stack and it is popped out when the function execution is over

( boundary condition is met ). Consider the following program :

#include<iostream> using namespace std; void func(int n) { if (n == 0) { // boundary condition return; } else { cout << n << " "; func(n-1); cout << n << " "; } } int main() { func(5); return 0; }

Can you predict the output of this program ?

We are calling the function with **n = 5**. So, the first **cout** statement is executed which prints **5** and then there is a recursive call to the function with **n = 4**. Thus, the state of the current call is stored in the system stack i.e the value of **n** and the address of the next statement after the function call ( in this case, 2nd cout statement ). This continues till **n** becomes **0** i.e boundary condition is met. At this point of time, we have printed **5 4 3 2 1**. Now, it’s time to pop out the contents of system stack in last-in-first-out (** LIFO **) order. Last instance stored in the stack was **n = 1** and the **address of 2nd cout statement**. So, the 2nd cout statement is executed and **1** is printed. When next instance is popped out, **2** is printed. This continues till all the function call instances are popped out.

Final output of the above program is : **5 4 3 2 1 1 2 3 4 5**

The usage of **system stack** is the most basic funda of **recursion**.

**Tower of Hanoi Problem**

**Tower of Hanoi** is a mathematical puzzle. It consists of three **PEGS** ( Source, Destination and Auxiliary ). Source peg consists of disks of different sizes such that they form a conical shape. The objective is to move all the disks from source to destination peg using an auxiliary peg with the following constraints :

**1 )** Only one disk can be moved at a time.

**2 )** We can never place a larger disk on top of a smaller disk.

Following figure illustrates the problem statement :

Suppose, we are given **n** disks on the source peg. We need to display all the **moves** which are required to move the disks from source peg to destination peg. Let’s formulate a recursive solution :

**1 )** Move top **n – 1** disks from source peg to auxiliary peg

**2 )** Move the only disk present in source peg to destination peg

**3 )** Move the **n – 1** disks from auxiliary peg to destination peg

Following program illustrates the recursive solution :

#include<iostream> #include<string> using namespace std; void solveTOH(int n, string src, string dest, string aux) { if (n == 1) { /* Boundary case ( only 1 disk present ) Move the disk from source to destination */ cout << " Move disk 1 from " << src << " to " << dest << endl; return; } else { /* Move top n-1 disks from src to aux */ solveTOH(n-1, src, aux, dest); /* Move the only disk from src to dest */ cout << " Move disk " << n << " from " << src << " to " << dest << endl; /* Move n-1 disks from aux to dest */ solveTOH(n-1, aux, dest, src); } } int main() { int no_disks = 3; solveTOH(no_disks, "SRC", "DEST", "AUX"); return 0; }

Suppose there are **3** disks on Source Peg and disks are numbered from top to bottom in increasing order i.e, top-most disk is numbered **1** and bottom-most disk is numbered **3** , then the solution is :

**Move disk 1 from SRC to DEST
Move disk 2 from SRC to AUX
Move disk 1 from DEST to AUX
Move disk 3 from SRC to DEST
Move disk 1 from AUX to SRC
Move disk 2 from AUX to DEST
Move disk 1 from SRC to DEST**