Need function explanation for Towers of Hanoi

Question

I am currently following a course and we were given to write a function for the Towers of Hanoi mathematical puzzle.

After following up some videos on youtube about it, I have compiled the following function:

def hanoi(n , source, target, spare):
    if n == 1:
        print("Move disk 1 from", source, "to", target)
    else:
        hanoi(n-1, source, spare, target)
        print ("Move disk", n, "from", source, "to", target)
        hanoi(n-1, spare, target, source)

Let's say I call this function as hanoi(3, "source", "target", "spare")

The output that I get is:

Move disk 1 from source to target
Move disk 2 from source to spare
Move disk 1 from target to spare
Move disk 3 from source to target
Move disk 1 from spare to source
Move disk 2 from spare to target
Move disk 1 from source to target

A friend recommended me to write down the code on paper in order to understand it but I fail to understand:

why is the function running the if clause when my n equals 3?
how is the computer actually running the program? What is the logic of going through the conditional statements? This baffles me also due to the fact that I put that print statement in between (because placing it in another place wouldn't have printed the right results)

Thanks a lot for your help and time!

EDIT: The Towers of Hanoi means having (by default) 3 poles. One pole would be the source pole (where the n disks would be originally placed), 2nd pole is the spare pole used as a helper and the 3rd pole is the target pole (where all the n disks would be originally placed). I used these variables to represent the poles and to be able to show the movement of the disks

The rules are: you can move 1 disk at a time and you cannot place a bigger disk on a smaller disk.

It would help a lot if you told what the variables `n , source, target, spare` mean. — M-Chen-3, Mar 09 '21 at 21:45
Why do you think that the `if` clause is run when `n` equals 3? — mkrieger1, Mar 09 '21 at 21:46
`why is the function running the if clause when my n equals 3?` it doesn't, it goes to `else` and runs `hanoi(3-1, source, spare, target)`. - then the new inner thing enters `else` as well, and runs `hanoi` with n=2-1. only then the thing is printed. - then the innermost call ends. so we get back to n=2 and it prints. then it runs n=2-1 hanoi again... and so on. "A friend recommended me to write down the code on paper in order to understand it but I fail to understand" - do what I did and analyse where it goes "down" and with what values. and when it goes back "up". — h4z3, Mar 09 '21 at 21:49
actually, if you trace it through (which I highly recommend: try pretending you're the Python interpreter and stepping through this one line at a time), the `print` statement in the `if` *is* the first one that gets executed. That's not because `3` passes the `n == 1` check, but because the `else` clause starts with the recursive call, so we go down the callstack to the `n = 1` case before anything else gets printed. — Robin Zigmond, Mar 09 '21 at 21:50
@mkrieger1 because the first line of the output is the command which is in the ``ìf``` clause — Osaka, Mar 09 '21 at 21:51
Why don't you just print `n` as well to see what's happening? — mkrieger1, Mar 09 '21 at 21:53
As others suggested, try to follow the order of the calls, pretending you're the python interpreter, even if the first print statement is from evaluating the `if` clause to `True`, it only does that after several calls to `hanoi`. Remember that this is a recursive function :) — Mateo Torres, Mar 09 '21 at 21:53
@mkrieger1 I printed ```n``` in different positions inside the ```hanoi``` and the only thing that made sense was to print it like this: ``` def hanoi(n , source, target, spare): if n == 1: print("Move diskkk 1 from", source, "to", target) else: hanoi(n-1, source, spare, target) print ("Move disssk", n, "from", source, "to", target) print(n) hanoi(n-1, spare, target, source) ``` After this, I was getting the ```n``` printed after the 2nd movement of the disks. Not sure what to follow in here — Osaka, Mar 09 '21 at 21:57
@h4z3 so that it is actually doing after running the 1st line from the ```else``` is to print the statement for ```hanoi(3-1, source, spare, target)``` and then go to the 3rd line in the ```else``` clause and run ```hanoi(n-1, spare, target, source)```? — Osaka, Mar 09 '21 at 22:02
Does this answer your question? [How to step through Python code to help debug issues?](https://stackoverflow.com/questions/4929251/how-to-step-through-python-code-to-help-debug-issues) — mkrieger1, Mar 09 '21 at 22:04
@ValentinDS it doesn't jump. each call `hanoi(...)` will enter the function with new values. it's basically as if you pasted `hanoi` code in the place of the call. The inner call starts from first line and checks the ifs again. and so on. When you exit the inner call, you return to where it was called — h4z3, Mar 09 '21 at 22:05

score 0 · Accepted Answer · answered Mar 09 '21 at 22:21

It seems the comments are too short to explain it clearly.

Each function call starts the function from its first line. And after the function ends, the code goes back to where it got invoked.

A friend recommended me to write down the code on paper in order to understand it

That's what we're gonna do here. Analyse the code line-by-line and see when it goes deeper and when it leaves.

hanoi(3, "source", "target", "spare") This will go to the else. And run hanoi with n=2
- So n=2, right? So we enter else again. And run hanoi again but with n=1
  - we go deeper! Now n=1, so we finally hit print! That's where Move disk 1 from to target came from! The function exits.
- We get back to where it was called. We did first hanoi in else. Now we hit another print. That's where Move disk 2 from source to spare comes from.
- We get to the next line. We run hanoi with n=1 again.
  - We're inside again. n=1, so we get into if and print Move disk 1 from target to spare and exit
- We got to where we invoked it (so we're in n=2 level) but we don't have any more lines to run. We exit
We're back to the top level. Now we hit the print Move disk 3 from source to target
Next line. Another call to hanoi, with n=2
- n=2, again: else, go deeper
  - n=1, print, exit
- we went back, so we print
- and go deeper again
  - n=1, print, exit
- exit
exit

To understand recursion, you can actually do debug printing when entering and leaving.

def hanoi(n , source, target, spare):
    print(f"   DEBUG: Starting hanoi({n}, {source}, {target}, {spare})")
    if n == 1:
        print("Move disk 1 from", source, "to", target)
    else:
        hanoi(n-1, source, spare, target)
        print ("Move disk", n, "from", source, "to", target)
        hanoi(n-1, spare, target, source)
    print(f"   DEBUG: Exiting hanoi({n}, {source}, {target}, {spare})")

>>> hanoi(3, "src", "trg", "spr")
   DEBUG: Starting hanoi(3, src, trg, spr)
   DEBUG: Starting hanoi(2, src, spr, trg)
   DEBUG: Starting hanoi(1, src, trg, spr)
Move disk 1 from src to trg
   DEBUG: Exiting hanoi(1, src, trg, spr)
Move disk 2 from src to spr
   DEBUG: Starting hanoi(1, trg, spr, src)
Move disk 1 from trg to spr
   DEBUG: Exiting hanoi(1, trg, spr, src)
   DEBUG: Exiting hanoi(2, src, spr, trg)
Move disk 3 from src to trg
   DEBUG: Starting hanoi(2, spr, trg, src)
   DEBUG: Starting hanoi(1, spr, src, trg)
Move disk 1 from spr to src
   DEBUG: Exiting hanoi(1, spr, src, trg)
Move disk 2 from spr to trg
   DEBUG: Starting hanoi(1, src, trg, spr)
Move disk 1 from src to trg
   DEBUG: Exiting hanoi(1, src, trg, spr)
   DEBUG: Exiting hanoi(2, spr, trg, src)
   DEBUG: Exiting hanoi(3, src, trg, spr)

See how the added print lines line up with what I wrote.

Yess, this is it. I also wrote it on the paper and I got it finally. And now reading your post makes even more sense. All along this time I was missing the idea of the recursion: calling a function within itself and when that happens, the function takes it again from the start. — Osaka, Mar 10 '21 at 20:58

Need function explanation for Towers of Hanoi

1 Answers1