4

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)
Kyle Strand
  • 15,941
  • 8
  • 72
  • 167
Scott Waldron
  • 41
  • 1
  • 3
  • 1
    Shoot, I don't know how to mark out my whitespace when posting my question... – Scott Waldron Mar 05 '13 at 02:54
  • when you are typing in a question or answer there is a code format button above the text box with some brackets {} as its icon, highlight your code then click that. – FoamyGuy Mar 05 '13 at 02:55
  • 2
    You're not asking a real question here. If this is "your" function, what don't you understand about it? Do you understand the Python syntax? Do you understand the underlying algorithm? – Kyle Strand Mar 05 '13 at 02:59
  • I'm not quite understanding the underlying algorithm I guess. Mainly why there is an if statement. I apologize, I'm still very new to this. – Scott Waldron Mar 05 '13 at 03:00
  • the if statement makes sure that ndisks is bigger than 1 – JeffS Mar 05 '13 at 03:06
  • If that's the case, why would it not be: if ndisks>1:? I'm just trying to figure this out – Scott Waldron Mar 05 '13 at 03:09
  • Sorry, I mistyped greater than or equal to 1. That's a common way to express that in python – JeffS Mar 05 '13 at 03:18
  • I've suggested an edit to clarify the nature of your question. – Kyle Strand Mar 07 '13 at 09:06
  • you should check out [this answer in - Tower of Hanoi: Recursive Algorithm](https://stackoverflow.com/a/58259294/7541700) – costargc Oct 06 '19 at 17:51

1 Answers1

4

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.

Mark Tolonen
  • 166,664
  • 26
  • 169
  • 251