# Towers of Hanoi - Detailed explanation on the algorithm's execution available?

https://app.dataquest.io/c/109/m/578/overview-of-recursion/4/towers-of-hanoi

Can someone please provide a detailed explanation of how the tower of Hanoi solution code works?

``````def solve_hanoi(num_disks, first_peg, middle_peg, last_peg):
if num_disks == 1:
# Base case
print("Move the top disk from peg {} to peg {}.".format(first_peg, last_peg))
else:
# General Case
# Instruction 1: Add code to solve the first subproblem
solve_hanoi(num_disks - 1, first_peg, last_peg, middle_peg)

# Second subproblem: Move disk num_disks from first_peg to last_peg
solve_hanoi(1, first_peg, middle_peg, last_peg)

# Instruction 2: Add code to solve the third subproblem
solve_hanoi(num_disks - 1, middle_peg, first_peg, last_peg)

solve_hanoi(3, 'A', 'B', 'C')
``````

Output:

``````Move the top disk from peg A to peg C.
Move the top disk from peg A to peg B.
Move the top disk from peg C to peg B.
Move the top disk from peg A to peg C.
Move the top disk from peg B to peg A.
Move the top disk from peg B to peg C.
Move the top disk from peg A to peg C.
``````

Iâ€™m having a lot of trouble following how the code arrives on this order of print statements past the first line. Could someone help me understand itâ€™s execution? Itâ€™s likely others are confused about it as well.

Thanks!

Recursion is not easy to understand and can take a lot of time and practice. So, donâ€™t worry if you are struggling with it. Itâ€™s a difficult concept to grasp for a lot of beginners.

But, you will have to spend some time breaking down the code in relation to what you need to do to understand it fully. Best way to do this is to just get a pen and paper and start writing the steps and the outputs for each line of code.

All 3 disks are on peg `A`. You want to move disks `1` and `2` to peg `B`. For that, you need to

• first move disk `1` to `C`
• then move disk `2` to `B`
• then move disk `1` to `C`.

Letâ€™s consider each of those in relation to the code.

## Disk `1` from `A` to `C`

``````solve_hanoi(num_disks - 1, first_peg, last_peg, middle_peg)
``````

In the above, `num_disks - 1` is `2` since we are moving 2 disks. Notice the order of the remaining arguments. The above is the same as -

``````solve_hanoi(2, A, C, B)
``````

With the function call, we go back to the `if` condition. Itâ€™s `False`. So, we end up on -

``````solve_hanoi(num_disks - 1, first_peg, last_peg, middle_peg)
``````

But now, the above equates to

``````solve_hanoi(1, A, B, C)
``````

The above function runs again, and this time the `if` condition is `True`. So, our `print` statement runs -

Move the top disk from peg A to peg C.

At this point, `first_peg` is `A` and `last_peg` is `C`.

So, our top disk, which was `1`, is now at `C`.

What happens now?

## Disk `2` from `A` to `B`

Our first code line

``````solve_hanoi(num_disks - 1, first_peg, last_peg, middle_peg)
``````

ran through each of its recursions and successfully returned that `print` statement. So, now we go to the next code line -

``````solve_hanoi(1, first_peg, middle_peg, last_peg)
``````

Now, this is going to be the confusing part and can take some time to understand.

You might expect that `first_peg = A`, `middle_peg = B` and `last_peg = C`.

However, that is not the case.

Letâ€™s go through the function calls again. Till now, we have called the function 3 times (the above call is the fourth one)

• First call (the original call)

• `first_peg = A`, `middle_peg = B` and `last_peg = C`

• Second call

• `first_peg = A`, `middle_peg = C` and `last_peg = B`

• Third call

• `first_peg = A`, `middle_peg = B` and `last_peg = C`

For the third call, we get our `return` statement. At this point, we go back to our second call. This is the part that can be confusing because we might think we would go all the way back to the first call. But thatâ€™s not the case.

Because our second function call has not yet had a `return` statement.

So, for our fourth call, we have

• `first_peg = A`, `middle_peg = C` and `last_peg = B`

That means, the above is the same as -

``````solve_hanoi(1, A, C, B)
``````

When the above runs, the `if` statement will be `True`. So, we will get our `print` output -

Move the top disk from peg A to peg B.

At this point, `first_peg` is `A` and `last_peg` is `B`.

So, our top disk, which is currently `2`, is now at `B`.

## Disk `1` from `C` to `B`

Letâ€™s look at the new order of our function calls -

• First call (the original call)

• `first_peg = A`, `middle_peg = B` and `last_peg = C`

• Second call

• `first_peg = A`, `middle_peg = C` and `last_peg = B`

• Fourth Call

• `first_peg = A`, `middle_peg = C` and `last_peg = B`
• Third call

• `first_peg = A`, `middle_peg = B` and `last_peg = C`

We had another `return` statement. So, our fourth function is done. We go back to our second function and move forward with the next line of code, which is -

``````solve_hanoi(num_disks - 1, middle_peg, first_peg, last_peg)
``````

At this point,

• `num_disks` is `2`
• `first_peg = A`, `middle_peg = C` and `last_peg = B`

So, the above code is going to be -

``````solve_hanoi(1, C, A, B)
``````

With the above call, we would have the `if` statement to be `True`. So, our `print` output would be -

Move the top disk from peg C to peg B.

At this point, `first_peg` is `C` and `last_peg` is `B`.

So, our top disk, which was `1` (since `first_peg` is `C`), is now at `B`.

Now we have

• Disk `3` on `A`.
• Disk `2` and `1` on `B`.

And we have to move the disk `3` from `A` to `C`

## Disk `3` from `A` to `C`

Our function calls are now -

• First call (the original call)

• `first_peg = A`, `middle_peg = B` and `last_peg = C`

• Second call

• `first_peg = A`, `middle_peg = C` and `last_peg = B`

• Fourth Call

• `first_peg = A`, `middle_peg = C` and `last_peg = B`
• Fifth Call

• `first_peg = C`, `middle_peg = A` and `last_peg = B`
• Third call

• `first_peg = A`, `middle_peg = B` and `last_peg = C`

Just a reminder, the second and first function calls still havenâ€™t had a `return` statement.

But, we reached the end of our code. There is nothing after that last code line, right?

What happens when we reach the end of our code?

Well, our second call simply ends (thereâ€™s no `return` statement) and we â€śjump backâ€ť to our first function call again (because thatâ€™s still a level above the second one)

For our first function call, the first line of code we ran was -

``````solve_hanoi(num_disks - 1, first_peg, last_peg, middle_peg)
``````

We already ran the above. And we went down that rabbit hole through all the recursive calls. Now, we move onto the next line of code -

``````solve_hanoi(1, first_peg, middle_peg, last_peg)
``````

Since we are back on our first call, we have -

• `first_peg = A`, `middle_peg = B` and `last_peg = C`

So the above code runs as -

``````solve_hanoi(1, A, B, C)
``````

With the above call, we would have the `if` statement to be `True`. So, our `print` output would be -

Move the top disk from peg A to peg C.

At this point, `first_peg` is `A` and `last_peg` is `C`.

So, our top disk, which was `3` (since `first_peg` is `A`), is now at `C`.

Now we have

• Disk `3` on `C`.
• Disk `2` and `1` on `B`.

And we have to move

• Disk `1` from `B` to `A`.
• Disk `2` from `B` to `C`.

## Disk `1` from `B` to `A`

Another call completed. Just like before, we move onto the next line of code for the first function call -

``````solve_hanoi(num_disks - 1, middle_peg, first_peg, last_peg)
``````

We have -

• `num_disks = 3`
• `first_peg = A`, `middle_peg = B` and `last_peg = C`

So the above code runs as -

``````solve_hanoi(2, B, A, C)
``````

`if` condition will not be `True`. Which code line will run now?

``````solve_hanoi(num_disks - 1, first_peg, last_peg, middle_peg)
``````

We have -

• `num_disks = 2`
• `first_peg = B`, `middle_peg = A` and `last_peg = C`

So the above code runs as -

``````solve_hanoi(1, B, C, A)
``````

With the above call, we would have the `if` statement to be `True`. So, our `print` statement would be -

Move the top disk from peg B to peg A.

At this point, `first_peg` is `B` and `last_peg` is `A`.

So, our top disk, which was `1` (since `first_peg` is `B`), is now at `A`.

I will stop at this point. The process basically keeps repeating for 2 more steps.

Take your time. Take out a pen and paper, and write along as you follow what I wrote above.

It will take time (and frustration), but make sure you spend time following through each line of code, and carefully think about which line of code runs when.

Please note: I have mentioned this already and you can see it as well - this is not easy. If you have follow up questions, you will have to be specific about what is confusing you and where based on what you have tried to understand so far. You will have to explain your thought process which points to where you are getting stuck again. Because, otherwise, I wonâ€™t be able to help you out more than the above.

But, definitely let me know if you find any mistake above.

1 Like

When struggling with code, a strategy is to step back and try to understand the concept/theory. After you have a firm grasp of theory, implementation is a breeze.

Hereâ€™s a playlist i really like, towers of hanoi included: Problem Solving - YouTube

Animations are really useful when learning recursion and dynamic programming.
For algorithms theory, he explains really well: https://www.youtube.com/playlist?list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O

1 Like

Thanks for your detailed explanation. I was able to follow along eventually.

Iâ€™m curious, when someone thinking up a recursive function do you map out all the calls the function will take to finish or just trust in the process of recursion?

Thisâ€™ll definitely take a few more knocks on the head to sink in as the the material on recursion is thin on this platformâ€¦

@hanqi Thanks for the references, Iâ€™ll check them out.