recursion problem

[u/Key_Cloud_7002]

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...

[u/pachura3]

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).