CODEWITHSUNDEEP
pythonrecursiontowers-of-hanoi
Scott Waldron
Scott Waldron

Reputation: 41

Towers of Hanoi Explanation

I'm a beginner to python and would like to know what the role of the if statement is in this Towers of Hanoi function:

def hanoi(ndisks, startPeg=1, endPeg=3):
    if ndisks:
        hanoi(ndisks-1, startPeg, 6-startPeg-endPeg)
        print "Move disk %d from peg %d to peg %d" % (ndisks, startPeg, endPeg)
        hanoi(ndisks-1, 6-startPeg-endPeg, endPeg)

hanoi(ndisks=4)

Upvotes: 4

Views: 3581

Answers (1)

Mark Tolonen
Mark Tolonen

Reputation: 178399

A recursive algorithm needs a terminal condition which usually represents the simplest case of the algorithm. For Towers of Hanoi the simplest case is when there are zero disks to move, don't do anything.

In Python, one condition of "falseness" is any numeric version of zero, so technically if anyone passed in a negative number to your algorithm it would fail, so it would be better to check for if ndisks > 0. This stops the recursion when ndisks==0.

If there are a positive number (n) of disks to move, the recursive algorithm is:

  1. Move n-1 disks from start peg to "other" peg.
  2. Move the nth disk from start to end peg.
  3. Move n-1 disks from "other" peg to end peg.

The above describes the rest of your code, with the terminal condition being zero disks.

Upvotes: 4

Related Questions