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!