Here's the question you clicked on:
sfox1288
Hey everyone, just finished the recursion lecture and I understand the idea of recursion, but had trouble understanding old man Grimson's explanation using the Hanoi towers. His code was: def hanoi(n,f,t,s): if n == 1: print 'move from ' + f + ' to ' + t else: hanoi (n-1,f,s,t) hanoi (1,f,t,s) hanoi (n-1,s,t,f) Can someone explain how Python interprets this code in plain english?
OK. Well I will show you what I found and how I came to understand it myself, in case it can help someone else. First, check out http://www.python-course.eu/towers_of_hanoi.php Also, it also helps to know that the number of moves will be (2^n) - 1. So for a tower of 3, there are 7 moves. When going through the def hanoi recursion function outlined in class, you should read it as follow. hanoi with n 3 does not meet the if statement, so it passes to the else. And will call in the following order. Look for my numbering to see where the 7 print statements come into play. hanoi (n-1[2],f,s,t) hanoi (n-1[1],f,s,t) 1. hanoi (1,f,t,s) -- > prints to move f to t 2. hanoi (1,f,t,s) -- > prints to move f to t hanoi (n-1[1],s,t,f) 3. hanoi (1,f,t,s) -- > prints to move f to t 4. hanoi (1,f,t,s) -- > prints to move f to t hanoi (n-1[2],s,t,f) hanoi (n-1[1],f,s,t) 5. hanoi (1,f,t,s) -- > prints to move f to t 6. hanoi (1,f,t,s) -- > prints to move f to t hanoi (n-1[1],s,t,f) 7. hanoi (1,f,t,s) -- > prints to move f to t I hope this helps anyone who is stuck on this example and helps you all learn recursion better.
"old man Grimson" xD!! I like him more than the others, I had a headache trying to understand that tower ... don't want to remember but try with a print in every linecode xD will help to find out what the heck that do xD
To move a tower of just one disk is simple: you just move the disk to another pin. (that's the `if n==1:` part). Now if you want to move a tower of let's say four disks, you can do it in three steps: First you move the top three disks to another pin, then you move the fourth disk to the 'target' pin and finally you move the three-disk tower back on top of the fourth disk. That is exacly what's happening in the `else` part of the function: hanoi (n-1,f,s,t) (move the top three (assuming n == 4) disks to one pin) hanoi (1,f,t,s) (move the fourth disk to the 'target' pin) hanoi (n-1,s,t,f) (move the top three disks back on top of the largest disk) Now, where recursion comes into play is the question "How do I move the three disk tower?" Again, you need three steps: First you move the top two disks to another pin, then you move the third disk to the 'target' pin and finally you move the two-disk tower back on top of the third disk. Sounds familiar?