CODEWITHSUNDEEP
pythonrecursion
KGS
KGS

Reputation: 297

Cant wrap my brain around towers of hanoi recursion in python

I understood recursions for factorials and other math cases, but this one is eluding me.

So, we have to break it into n-1 down to the base case, but I don't see how the code is breaking down to output all the steps?!

1   def printMove(fr, to):
2       print('move from ' + str(fr) + ' to ' + str(to))
3   
4   def Towers(n, fr, to, spare):
5       if n == 1:
6           printMove(fr, to)
7       else:
8           Towers(n-1, fr, spare, to)
9           Towers(1, fr, to, spare)
10          Towers(n-1, spare, to, fr)
11  Towers(3,'t1','t3','t2')

move from t1 to t3
move from t1 to t2
move from t3 to t2
move from t1 to t3
move from t2 to t1
move from t2 to t3
move from t1 to t3

How does this work? Do I need to be able to grok this, or does writing the code at a high level by coding the general idea knowing the details will work out suffice?

Upvotes: 0

Views: 521

Answers (3)

pjs
pjs

Reputation: 19855

Sometimes recursion involves what I like to call a "leap of faith". Moving a single disk with nothing on top of it from one tower to a destination is easy, you just move it. So let's assume that the recursive function hanoi can move a pile of n disks from the current location src to a specified destination dst using a spare tower hlp as needed. Once we make the assumption that it can be done, it's easy to see that what we need to do is move the pile of size n-1 off the bottom disk and onto the spare tower, trivially move the bottom disk to the destination, and then move the pile of n-1 disks from the spare tower back onto the bottom disk at the destination. Mission accomplished! Alfasin's code rewrite shows this clearly once you realize that calling the hanoi function with 0 disks is effectively a no-op, so when there is a single disk it gets moved but the two recursive calls bracketing bracketing that move do nothing.

Upvotes: 0

Nir Alfasi
Nir Alfasi

Reputation: 53535

Reducing the boilerplate might help with grasping the recursion:

def hanoi(n, src, hlp, dst):
    if n > 0:
        hanoi(n-1, src, dst, hlp)
        print("moving disc " + str(n) + " from " + src + " to " + dst)
        hanoi(n-1, hlp, src, dst)
# call with:
hanoi(3, 'src', 'hlp', 'dst')

Explanation:
The recursion is based on moving the first n-1 discs from the "source" to "helper" (middle tower) - which is done by using the "destination" tower as the "helper". This is done in the line:
hanoi(n-1, src, dst, hlp)

Then move the biggest ring (n) from the "source" to the "destination" (which is done in the "print").

And then again, recursively, move the n-1 rings from the "helper" to the "destination" while using the "source" pole as the "helper": hanoi(n-1, hlp, src, dst)

Upvotes: 2

dansalmo
dansalmo

Reputation: 11696

Knowing the details of how code works is necessary for fixing problems with the code when they happen. It is nice if you code a general algorithm that you were given or found and it happened to work without much trouble. Struggling through the design and development on your own is much harder. Not knowing how your code works will prevent you from fixing it.

Upvotes: 0

Related Questions