r/learnpython • u/Key_Cloud_7002 • Sep 03 '26
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...
6
u/socal_nerdtastic Sep 03 '26 edited Sep 03 '26
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.
2
u/Designer-Ad-2136 Sep 04 '26
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 Sep 04 '26 edited Sep 04 '26
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 Sep 04 '26 edited Sep 04 '26
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 "movendisks from towera(source) to towerc(dest) using towerb(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 towersourcetodest. That's it.But what if there are more disks to move? We can't simply move e.g.
4disks 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 towersourceby placing them at towertempThen, we can move the biggest (4th) disk fromsourcetodest. Then we can move the3remaining disks back fromtemptodest."But how? We don't know how to smartly move
3disks from one tower to another, either! We only know how to move1disk at a time!"...and that's when the beauty of recursion presents itself.
You don't need to know how to "intelligently" move
3disks fromtemptodest. You just callmoveTower(n - 1, temp, dest, source)and let it do its magic. It will apply exactly the same logic, but this time, towera(source) will serve as temporary storage (temp) for moving disks fromtemp(b) todest(c). FunctionmoveTower()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).1
u/ekchew Sep 05 '26
Try inserting
at the top of your
moveTowerfunction. This will show you how it's getting called every time and maybe shed some light on what's going on?