Towers of Hanoi is a classic example of recursion in computer science. You will find a lot of links on the web where towers of hanoi is well explained. Here, I will directly give you the recursive pseudo code, analysis of time complexity, number of function invocations and number of movements

For simplicity let us represent towers of hanoi as **TOH**. Let the three towers be **x**, **y**, and **z** respectively. Let number of disk/rings be **n**.

**Problem Statement:** Move all the **n** disk from tower **x** to tower **y** using tower **z**.

**Recursive Function**:

TOH(n, x, y, z)

{

if(n>1){

TOH(n-1, x, z, y);

move top disk of 'x' to 'y'

TOH(n-1, z, y, x);

}

else if (n == 1){

move disk of x to y;

}

}

**Time Complexity of Towers of Hanoi**:

Time Complexity equation would be: `T(n) = 2T(n-1) + 1; (1 is constant)`

Base condition for Time Complexity: `T(n) = 1 at n = 0`

(Time complexity is 1 when there is no disk at all)

Solving the equation using substitution will give us the time complexity as **O(2 ^{n})**

**Number of Function Invocations I(n): ** i.e total number of times the **TOH()** function has been called can be found out by using the equation `I(n) = 2I(n-1) + 1`

with base condition being `I(n) = 1 at n = 1`

. Solving the equation by substitution would give us

**I(n) = 2 ^{n}-1**

**Number of movements required for moving n disk from x to y using z M(n):**

This can be found out by using the equation

`M(n) = 2M(n-1) + 1`

with base condition being `M(n) = 0 at n = 0`

. Solving the equation by substitution would give us**M(n) = 2 ^{n}-1**

If you have doubts over this then you are advised to read some good materials about towers of Hanoi (with respect to Computer Science) and come back here to verify the result yourself.

Also Read: Clear the confusion over string declaration.

Also Read: Examples of complicated declaration in C like char (*(*x())[])()