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.