I am learning Prolog and attempt get a more detailed understanding of the Tower of Hanoi solver (as described by Fisher) in order to understand recursion better.
This post is a bit lengthy, but I don’t know how to describe my confusion more concise.
The code for the Hanoi solver is as follows (I added a print statement in the recursion to see better what’s happening):
move(1, X, Y, _) :-
write(' Move top disk from '), write(X), write(' to '), write(Y), nl.
move(N, X, Y, Z) :-
N>1,
M is N-1,
write('Level: '), write(N), nl,
move(M,X,Z,Y),
move(1,X,Y,_),
move(M,Z,Y,X).
This works fine. Let’s use N=3
for example to evaluate it:
?- move(3,left,right,center).
Level: 3
Level: 2
Move top disk from left to right
Move top disk from left to center
Move top disk from right to center
Move top disk from left to right
Level: 2
Move top disk from center to left
Move top disk from center to right
Move top disk from left to right
true
In order to really understand this, I attempted to write the recursion myself and in the recursion rule I came up with another order of the move statements:
move(N, X, Y, Z) :-
N>1,
M is N-1,
write('Level: '), write(N), nl,
move(M,X,Z,Y),
move(M,Z,Y,X),
move(1,X,Y,_).
Let’s run it again with N=3
:
?- move(3,left,right,center).
Level: 3
Move top disk from left to right
Level: 2
Move top disk from left to center
Move top disk from left to right
Move top disk from right to center
Level: 2
Move top disk from center to right
Move top disk from center to left
Move top disk from left to right
true
When doing the moves it’s easy to see that these instructions are wrong. But why? I though I first always do the “real” move and then call the recursions.
Thanks for pointers!