Explain this Towers of Hanoi solution (written in python)

Question

I am trying to understand this particular solution of Towers of Hanoi problem. It is a recursive solution.

A = [5, 4, 3, 2, 1]
B = []
C = []

def move(n, source, target, auxiliary, frm):
print('n here : ', n)
if n > 0:
    print('frm : ', frm, n)

    # move n - 1 disks from source to auxiliary, so they are out of the way
    move(n - 1, source, auxiliary, target, '1')

    # move the nth disk from source to target
    target.append(source.pop())

    print('n:', n)

    # Display our progress
    print(source, target, auxiliary, '##############', sep = '\n')

    # move the n - 1 disks that we left on auxiliary onto target
    move(n - 1, auxiliary, target, source, '2')

# initiate call from source A to target C with auxiliary B
move(5, A, C, B, '0')

You can see it live here https://repl.it/JUzY/0

After the first line of ######### gets printed, the value of n = 0, becomes 2. How does this happen? Am I missing out some concept of recursion ? Help me in understanding this.

Answer 1

You need to understand scope. You say "the value of n = 0, but suddenly it becomes 2". But there is more than one "n", because the scope of n is the method. Each time move gets called, that method call has its own instance of n with its own value.

At the bottom of the script, you call move(5, A, C, B, '0'). Inside that call, n == 5. The first thing that does is call move(n - 1, source, auxiliary, target, '1'). Inside that call, n == 4. But when it eventually returns, n in the original function call is still 5.

---

A good way to understand how recursion works, is to work through the program execution by hand, using sheets of paper. I'm going to use a Post-It note for function calls, and a notebook for output. You also have your "model", in the form of the lists A,B,C. Since elements move around, you could represent those elements with scraps of paper or scrabble tiles.

Start with the intial move(4, A, C, B, '0'). (I'm starting at 4 because the number of steps grows rapidly). Since we are calling a function, take a new post-it to represent the function call, and write on it:

n = 4
source = A
target = C
auxiliary = B
frm = '0'

Now work through the code of move doing what it says. Write any print output on this one.

When you reach the call to move(n - 1, source, auxiliary, target, '1'), make a note on the post-it of the line number you're at, then get a new post-it, and write the values that are going into it:

n = 4     (because 4 - 1)
source = A
target = B  (caller's auxiliary)
auxiliary = C (caller's target)
frm = '1'

Place this on top of the previous post-it. You are not allowed to look at the covered up post-it until it's revealed again. Keep doing this, and you'll end up with a stack of five post-its.

The fifth post-it has n = 0. Now when you step through its code, because it starts with if n > 0:, the call returns immediately. This function call is over, so tear up that one post-it and throw it away. The values of n etc. in that post-it have no effect on the other post-its.

You made a note of the line-number you were at, so carry on executing the code by hand from that line. You will produce some output, then call move again -- use post-its for this move too, again covering up the current post-it and growing your stack until you make a call with n == 0 and can remove an item from the stack.

If you keep doing this, you'll see the stack grow and shrink several times, you'll reach the original post-it once, do its print, then grow the stack again, then reach the original post-it again, and finally finish.

---

The stack of post-it notes is an exact model of the execution stack of a program's runtime. When you see stack traces (even of non-recursive programs), this is what they represent. Each post-it is a stack frame, and local variables have a scope that is restricted to that stack frame.

---

The recursive solution to Hanoi can be expressed in English as:

• To move a stack of size zero, do nothing
• To move a bigger stack from src to destination via auxiliary:
  • First move n-1 discs from src to auxiliary (to get them out of the way)
    • do that the same way we are doing this.
  • Then move the revealed disc to destination
  • Then move the n-1 discs from auxiliary to destination, using src as a spare peg
    • do that the same way we are doing this