r/learnpython • u/Key_Cloud_7002 • 12h ago
recursion problem
I'm trying to teach myself python using John Zelles book. On the 13th chapter it gives this example of recursion I'm trying to understand:
def moveTower(n, source, dest, temp):
if n ==1:
print("move disk from , " , source , "to", dest)
else:
moveTower(n-1, source, temp, dest)
moveTower(1, source, dest,temp)
moveTower(n-1,temp,dest,source)
def hanoi(n):
moveTower(n , "a", "c","b")
hanoi(3)
The code is first assiging the variables A to source then C to dest then b to temp but do the lines moveTower(n-1, source, temp, dest) and moveTower(n-1,temp,dest,source) work? Would it be moveTower(3-1, a,b,c)? How exactly are they outputting a to c then a to b then c to b and b to a , etc...
1
u/jmooremcc 12h ago
Your IDE should have a debugger that will allow you to set breakpoints and single step through your code.
1
u/Designer-Ad-2136 8h ago
This implementation is confusing because it recursively outputs instructions for the solution. It is not actually modelling the problem at all. Tower of hanoi is not a great problem for teaching recursion imo
1
u/recursion_is_love 4h ago edited 4h ago
It is possible and helpful to trace the code by pen and paper on zero disk, one disk and two disk. You will get it when you notice the dejavu.
You invest your time once and the understanding remains for a long time. For me, the convenience of the debugger mad it easy to skip the "pause and think" moment.
1
u/pachura3 1h ago edited 1h ago
The code is first assiging the variables A to source then C to dest then b to temp but do the lines moveTower(n-1, source, temp, dest) and moveTower(n-1,temp,dest,source) work? Would it be moveTower(3-1, a,b,c)? How exactly are they outputting a to c then a to b then c to b and b to a , etc...
To understand recursion you have to stop thinking about variables and start thinking about the big picture. About the semantics of the problem. About the generalized solution.
moveTower(n, "a", "c", "b") means "move n disks from tower a (source) to tower c (dest) using tower b (temp) as temporary storage".
But what does moveTower() actually do?
When we need to move exactly one disk (n == 1), the action is trivial: physically move that disk from tower source to dest. That's it.
But what if there are more disks to move? We can't simply move e.g. 4 disks from one tower to another at the same time, as this would violate the main rule stating that no bigger disk can ever be placed over a smaller one.
So, in fact, we need to temporarily remove all the disks but the biggest one (n - 1, in our example == 3) from tower source by placing them at tower temp Then, we can move the biggest (4th) disk from source to dest. Then we can move the 3 remaining disks back from temp to dest.
"But how? We don't know how to smartly move 3 disks from one tower to another, either! We only know how to move 1 disk at a time!"
...and that's when the beauty of recursion presents itself.
You don't need to know how to "intelligently" move 3 disks from temp to dest. You just call moveTower(n - 1, temp, dest, source) and let it do its magic. It will apply exactly the same logic, but this time, tower a (source) will serve as temporary storage (temp) for moving disks from temp (b) to dest (c). Function moveTower() will keep calling itself, deeper and deeper, until it reaches one of its dead ends (n == 1) and some single disk can be physically moved. Then it will slowly crawl out of the deeply nested recursion.
Neat, huh?
In other words, you only need to define what does the function do at the deepest level of the recursion (n == 1) and how to generalize it to handle any arbitrary number of disks (n).
5
u/socal_nerdtastic 12h ago edited 12h ago
Drop this code into pythontutor.com or another visualizer where you can see the code execution step by step.
I'm not really understanding where you are stuck, but a common hangup is that people don't realize that making a recursive call invokes a whole new copy of the function. So when you call moveTower from inside moveTower, python makes a whole new copy of the moveTower function and that will run completely independently from the first one.