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

Suppose,

So, in the above series,

Observe that

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

Boundary Case :

Following program implements the recursive algorithm to compute

**#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**

The most crucial thing to remember while framing a recursive solution to a problem is to follow the

( Keep It Simple ) principle. You would have already noticed how simple is the recursive solution to the Tower of Hanoi problem. Start thinking with simple input cases and then generalize the algorithm.