In this piece, we will

1. Identify and break down the sub-problems

2. Derive the recurrence relation

3. Identify the base case, arguments for the recursive function

4. Draw the recursion tree

Let's dive into the Tower of Hanoi problem:

The objective is to move an entire stack of disks from the source to another destination. Three simple rules are followed:

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

2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. In other words, a disk can only be moved if it is the uppermost disk on a stack.

3. No larger disk may be placed on top of a smaller disk.

Usually, the Towers of Hanoi problem is presented with the scenario of moving 3 disks.

It is a good place to start to test whether the problem can be solved by breaking it into sub-problems. With 3 disks we can even try to derive the recurrence formula faster.

To move all 3 disks from the source to the destination:

1. We would need to move the first 2 disks from the source to the auxiliary.

2. Now, we can move 3rd disk from the source to the destination. (Hoorah!)

3. Again we would need to move the first 2 disks back from auxiliary to destination to complete the process!

Tower(3, src, dest) \= Tower(2, src, aux)+[Move 3rd disk to dest]+Tower(2, aux,dest)

Now the problem is reduced to solving the transfer of moving 2 disks from the source to auxiliary

1. First, we would need to move 1st disk from the source to the destination

2. Now, we can move 2nd disk from the source to the auxiliary!

3. Again we would need to move 1st disk back from the destination to auxiliary

Tower(2, src, aux) \= Tower(1, src, dest)+[Move 2nd disk to aux]+Tower(1, dest,aux)

Now we can easily recognise that the base case is n = 1.

We can return after moving the specific disk to its required stop.

Let's try to summarise the 3 steps into a formula:

We can see that the recurrence function would need to have the disk number, source, destination, and auxiliary to output the movement of each disk throughout.

Tower(n, src, dest, aux)= Tower(n-1, src, aux, dest)+ Move nth disk to dest + Tower(n-1, aux, dest, src)

Given all the information we have come up with, we can now write the pseudocode

func towersOfHanoi(n, src, dest, aux){
   if n == 1 {
     move disk n from src to dest
     return
   }
   towersOfHanoi(n-1 , src, aux, dest)
   move disk n from src to dest
   towersOfHanoi(n-1 , aux, dest, src)
}

Let's chart the flow of entire problem using a recursion tree

Beautifully lucid, isn't it?

A perfect in-order tree traversal to solve the Towers of Hanoi problem!

PS: Shoutout to Kunal Kushwaha for putting in so much effort to make DSA content on youtube that helps Devs to upskill without falling into tutorial hell spirals!

Applied your step by step by recursion guide to solving this question by myself :D

Taking my first step to learning in public and contributing to the supportive Dev community!