Difficulty understanding Python's recursive implementation of Hanoi Towers

Question

I've found a Python code online for the Hanoi Towers problem. The code works, but I'm having difficulty understanding it. Here it is:

def hanoi(n, source, helper, target):
    if n > 0:
        # move tower of size n - 1 to helper:
        hanoi(n - 1, source, target, helper)
        # move disk from source peg to target peg
        if source:
            target.append(source.pop())
        # move tower of size n-1 from helper to target
        hanoi(n - 1, helper, source, target)


source = [2, 1]
target = []
helper = []
hanoi(len(source), source, helper, target)

print (source, helper, target)

I'm having difficulty with the last part:

hanoi(n - 1, helper, source, target)

As far as I can understand, the only moving that happens is via the target.append(source.pop()) line. When we do it with a simple list of [2,1], after we move 1 to the target list, it somehow moves 1 to the helper list, but how???

The way I see it, Here's how to program runs: it reaches n = 0, does nothing, returns to n = 1, moves 1 to the target, then it reaches my difficult point, and executes

hanoi(n - 1, helper, source, target)

but since n-1 = 0, it does nothing, and then it should move on to n = 2, with source = [2], helper = [], target = [1]. But when I use prints on the program, I see that after my difficulty point and before n = 2, somehow the function does move 1 to the helper, and the situation is source = [2], helper = [1], target = []

How does it do it, even though n = 0? it has a condition that only if n>0 it executes? How can I use prints to see what's going on in that moment?

Answer 1

I've inserted standard tracing print statements: every time we enter or exit the routine, and at critical processing junctions. I've also thrown in indentation to help show the call levels.

There's also a bit of a cheat to illustrate the problem for you: I added a character label to each stack, and then reduced n by one so that we never move those labels. This allows you to see exactly which stack is in each role on every call.

The output should show you just what gets moved on each call, and where the recursion takes place in all the disk shuffling. When you get the idea for 2 disks, try it with 3. When you start to understand, extend it to 4 and comment out one or two of the tracing statements -- maybe just watch the moves.

indent = ""

def hanoi(n, source, helper, target):
    global indent
    indent += "  "
    print (indent, "ENTER", n, source, helper, target)
    if n > 0:
        # move tower of size n - 1 to helper:
        hanoi(n - 1, source, target, helper)
        # move disk from source peg to target peg
        if source:
            print (indent, "MOVE disk", source[-1], "from", source[0], "to", target[0])
            target.append(source.pop())
        # move tower of size n-1 from helper to target
        hanoi(n - 1, helper, source, target)

    print (indent, "LEAVE", n, source, helper, target)
    indent = indent[:-2]


source = ['A', 2, 1]
helper = ['B', ]
target = ['C', ]

print (source, helper, target)
hanoi(len(source)-1, source, helper, target)
print (source, helper, target)

Output:

['A', 2, 1] ['B'] ['C']
   ENTER 2 ['A', 2, 1] ['B'] ['C']
     ENTER 1 ['A', 2, 1] ['C'] ['B']
       ENTER 0 ['A', 2, 1] ['B'] ['C']
       LEAVE 0 ['A', 2, 1] ['B'] ['C']
     MOVE disk 1 from A to B
       ENTER 0 ['C'] ['A', 2] ['B', 1]
       LEAVE 0 ['C'] ['A', 2] ['B', 1]
     LEAVE 1 ['A', 2] ['C'] ['B', 1]
   MOVE disk 2 from A to C
     ENTER 1 ['B', 1] ['A'] ['C', 2]
       ENTER 0 ['B', 1] ['C', 2] ['A']
       LEAVE 0 ['B', 1] ['C', 2] ['A']
     MOVE disk 1 from B to C
       ENTER 0 ['A'] ['B'] ['C', 2, 1]
       LEAVE 0 ['A'] ['B'] ['C', 2, 1]
     LEAVE 1 ['B'] ['A'] ['C', 2, 1]
   LEAVE 2 ['A'] ['B'] ['C', 2, 1]
['A'] ['B'] ['C', 2, 1]