Hanoi Tower - How does this recursive solution work?

Question

Could someone explain to me the logic of this recursive function? I’m not getting the idea from if down. The code solves the problem of the Tower of Hanoi:

def toweOFhanoi(disc,ori,dest,aux):
    if disc == 1:
        print('Move disc {} from tower {} to the tower{}'.format(disc,ori,dest))
        return

    toweOFhanoi(disc - 1,ori,aux,dest)
    print('Move disc {} from tower {} to the tower {}'.format(disc,ori,dest))
    toweOFhanoi(disc - 1,aux,ori,dest)
    print('Move disc {} from tower {} to the tower {}'.format(disc,ori,dest))

Answer 1

First, the function is wrong, there’s a print the plus and the second recursive call changed the order of the towers:

def hanoi(disc, ori, dest, aux):
    if disc == 1:
        print('Move disc {} from tower {} to the tower {}'.format(disc, ori, dest))
        return

    hanoi(disc - 1, ori, aux, dest)
    print('Move disc {} from tower {} to the tower {}'.format(disc, ori, dest))
    hanoi(disc - 1, aux, dest, ori)

---

Now to the problem. The problem of the Tower of Hanoi consists of moving a number of disks from one tower to another (with a third auxiliary tower). The discs have different sizes, and one disc can never be placed on top of another smaller than it. Moreover, only one disc can be moved at a time.

The if deals with the most basic case: when there is only 1 disk. In this case the solution is easy: move the disk from the initial tower to the final, ie from the origin (ori) to fate (dest).

But what if we have more than one disk? In this case, assuming that the towers are A (origin), B (destination), and C (auxiliary), the idea of the algorithm is (for N disks):

1. solve the problem for N - 1 disks, only moving from A to C (ie using C as target and B as auxiliary)
2. move 1 disk from A to B (from source to destination)
3. solve the problem for N - 1 disks, only moving from C to B (i.e., C is the source, B is the destination and A is the helper)

That’s what recursive calls are doing. hanoi(disc - 1, ori, aux, dest) corresponds to step 1 above. The print soon after is step 2, and hanoi(disc - 1, aux, dest, ori) is step 3.

The big trick is that each of these recursive calls can generate other recursive calls, until they arrive in the case where it only has a 1 disk, which is when they return and return printing the respective steps.

For example, if I have 5 disks and want to move them from A to B (where C is the auxiliary tower). The idea is:

• move 4 disks from source (A) to auxiliary (C)
• move disk 5 to target (B)
• move the 4 disks that are in auxiliary (C) to destination (B)

But how to do the first step (move 4 disks from A to C)? Simple, I call the function again for 4 disks (N - 1), only considering that C is the destination and B is the auxiliary. Then she will do all three steps above, but considering this new context (4 disks, destination is C and B is auxiliary). The same thing for the third step (only now are 4 disks whose origin is C, destination is B and the auxiliary is A).

---

For example, if I have 3 disks, the execution looks like this:

• first I solve the problem for 2 disks, moving from A to C, using B as auxiliary
  • resolvo to 1 disk, moving from A to B, using C as auxiliary
  • movement 2 from A to C
  • solve to 1 disk, moving from B to C, using A as auxiliary
• I move disk 3 from A to B
• resolvo for 2 disks, moving from C to B, using A as auxiliary
  • solve to 1 disk, moving from C to A, using B as auxiliary
  • movement 2 from C to B
  • resolvo to 1 disk, moving from A to B, using C as auxiliary

Calling in the code would be:

hanoi(3, 'A', 'B', 'C')

Exit:

Move disc 1 from tower A to the tower B
Move disc 2 from tower A to the tower C
Move disc 1 from tower B to the tower C
Move disc 3 from tower A to the tower B
Move disc 1 from tower C to the tower A
Move disc 2 from tower C to the tower B
Move disc 1 from tower A to the tower B

^{See the code running on Ideone.com}

What can be confusing is that with each recursive call, the towers used as source, destination, and auxiliary change. But the logic is the same for calls (move N - 1 disks from source to auxiliary, move 1 disk from source to destination, move N - 1 disks from auxiliary to destination).

Remembering also that for N disks, the solution requires 2^N - 1 steps, and depending on N, that whole amount of recursive calls can cause a pile overflow. The exact amount depends on the value of the recursion limit (that can be changed), but the value default it’s not that big (example).

Answer 2

This is a case that for you to understand how the function was developed to solve the Hanoi tower you need to consider that there is already a function to solve the Hanoi tower. Confused? No, recursive.

Let’s consider that our goal is to pass the disks from A to C, being B our auxiliary. For the result to be valid, disk 3 must be the first in C, correct? To move disk 3 to C we need to move disks 1 and 2 to B first.

The problem of moving disks 1 and 2 to B is also a Hanoi tower, but now 2 disks:

And in that case Tower C will be our auxiliary. Remember I said at the beginning that you need to consider that there is already a function that solves the tower of Hanoi? So we call her to solve the tower with two disks and we’ll have:

Now just move disk 3 to C.

To move discs 1 and 2 to C we will have another Hanoi tower with 2 disks to solve, now with the origin in B, destination in C, with tower A as auxiliary. Luckily we already have a function that solves that.

Once that’s done, we’ll have the tower completely resolved.

That is, to solve the tower for 3 disks, changing from A to C, with auxiliary B, we made:

1. We solved the Hanoi tower with 2 discs from A to B, with auxiliary C;
2. We move disk 3 from A to C;
3. We solved the Hanoi tower with 2 discs from B to C, with auxiliary A;

Correct? Now review the code (simplified):

def tower_of_hanoi(disc, orig, dest, aux):

    # 1. Resolve a torre de Hanoi para n-1 discos, movendo para o disco auxiliar:
    tower_of_hanoi(disc-1, orig, aux, dest)

    # 2. Move o maior disco para a torre destino:
    print('Move disc {} from tower {} to the tower {}'.format(disc, orig, dest))

    # 3. Resolve a torre de Hanoi para n-1 discos, movendo da torre auxiliar para a destino:
    tower_of_hanoi(disc - 1, aux, ori, dest)

Okay, the magic is done.

But then you think, "Okay, but how to solve the Hanoi tower for 2 disks?". Simple, it’s the same logic (so it’s recursive). When solving the tower for 2 disks you before resolve for 1 disk (n-1), however, when you own only 1 disk not have much secret, you can move it freely. With this we create our recursive stop condition: if the tower has only 1 disk, move it and finish the function.

This is implemented by if:

# Se possuir apenas 1 disco:
if disc == 1:
    # Move o disco e finaliza a função
    print('Move disc {} from tower {} to the tower{}'.format(disc, ori, dest))
    return

So, to solve a tower of 3 disks he needs to know how to solve one of 2 disks; to solve the 2 disks need to know how to solve one of 1 disk; he knows how to solve 1 disk. This will work for any number of disks and three towers.

Behold Determine the nth Fibonacci term with recursion for more information on how recursion works.

Answer 3

A good way to understand how recursive methods work is to understand its pattern.
(It makes it much easier if you take the formula directly, but anyway)

(Recursion is part of an exact module: Mathematical analysis)

First we need to find the pattern.

To move n disk(s) how many moves are needed?
disk 1=1 movement
disc 2=2 movements
disc 3=4 movements
total movements for 3 disks? 7
total movements for 2 disks? 3
total movements for 1 disk? 1

So we can simplify it as scientific notation (f(x)=2**x - 1) to know how many moves it takes to complete the puzzle with X disks.

But now what? How do we make this function recursive?

If a = {1, 3, 7} then how do you get a2 from a1? Simple! a2=2*a1+1

Then we come to the formula of the method!

And finally, how carambola works this method?

def recursivo(n, aux=0):
        if n == 0:
            return aux
        aux+=metodo(n-1, 1)
        aux+=metodo(n-1)
        return aux