I understand what the recursive algorithm to solve Tower of Hanoi is doing:
For example if we have three pegs ( A , B , C ) and we want to move 3 discs from A -> C , we move disc 1 and 2 to B and then move disc 3, the biggest one, to peg C, then move discs 1 and 2 that we moved earlier to B, to C. This algorithm is expressed in pseudo in the following way:
FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
move disk from source to dest
ELSE:
MoveTower(disk - 1, source, spare, dest)
move disk from source to dest
MoveTower(disk - 1, spare, dest, source)
END IF
I make the call: MoveTower(3,A,C,B) which would call MoveTower(2,A,B,C) which would call MoveTower(1,A,C,B) which would finally reach the base case which would move A -> B.
This is where I am confused. When arriving at the base case, we move the top disk on A to B ( in a single shot) How does the recursion move everything else? How does the "backing out phase" move the other discs( which is in this case all discs but the biggest to B)? Isn't it only moving the top disc at the base case?
For example I know in the factorial function after we reach the base case, the recursion "returns" a value which is passed on to the previous call which is passed on to the previous call all the way until the top call. At each level its waiting for its recursion to come back.
Can someone help me understand how the recursion accomplishes anything in the first MoveTower(disk - 1, source, spare, dest) call other than reaching the base case?
Thanks
Just be patient, and be precise.
FUNCTION MoveTower(disk, source, dest, spare):
1. IF disk == 0, THEN:
2. move disk from source to dest
3. ELSE:
4. MoveTower(disk - 1, source, spare, dest)
5. move disk from source to dest
6. MoveTower(disk - 1, spare, dest, source)
7. END IF
Imagine yourself being a human computer, sitting at a nice comfy desk, with paper and pencils aplenty.
To call a function you copy the function recipe onto an empty sheet of paper and place it in front of you.
To call another function you copy that function's recipe onto an empty sheet of paper and place this sheet of paper on the stack of sheets of paper in front of you. It does not matter whether you are calling the same function or not, because you are working with its recipe's copy.
CALL MoveTower(3, A, C, B)
==> MoveTower_recipe{ disk=3, source=A, dest=C, spare=B }
| 1. IF disk==0, THEN:
= IF 3 ==0, THEN:
....
3. ELSE:
4. CALL MoveTower(disk - 1, source, spare, dest)
= CALL MoveTower(3-1, A, B, C)
==> MoveTower_recipe{ disk=2, source=A, dest=B, spare=C }
| 1. IF 2 == 0 THEN:
.....
3. ELSE:
4. CALL MoveTower( 1, A, C, B)
==> MoveTower_recipe{ disk=1, source=A, dest=C, spare=B }
| 1. IF 1 == 0 THEN:
3. ELSE:
4. CALL MoveTower(0, A, B, C)
==> MoveTower_recipe{ disk=0, source=A, dest=B, spare=C }
| 1. IF 0 == 0 THEN:
2. ___move disk{0} from source{A} to dest{B}___ (*1)
7. END IF
<==
5. ___move disk{1} from source{A} to dest{C}___ (*2)
6. CALL MoveTower( 0, C, B, A)
==>
.....
.....
See? The copies of the MoveTower function recipe are stacked on top each other, with each copy holding its own actual values of the function's named parameters (here the stack grows - visually - down, but on your desk the stack of papers would be piling up).
You work along the recipe on the top sheet of paper, making notes on its margins as to where you currently are along the recipe's lines, and the values of various named parameters and / or named internal variables (if any) and / or interim unnamed values (like disk - 1).
When you're done with the top sheet of paper, you throw it away, not before copying its return value (if any) to the sheet of paper now on top, at the place where you were before you entered the now discarded recipe's copy.
You can also note the input-output instructions performed by you the human computer, following the (copies of) the function recipes, on yet another sheet of paper on your side, recording the effects on the Real World your program would be having (marked with (*1), (*2), etc., above).
That's it.
The state of your computation is recorded in the margins on each recipe copy in the stack.
When you've reached the base case, not only have you produced the first output instruction; you've also piled up a whole lot of function recipes' copies in front of you, each with its associated data and state (current point of execution).