Tower of Hanoi
The tower of Hanoi (Wikipedia) is a really neat example for recursion. Often recursion is taugt with the factorial or the Fibonacci numbers. Both cases are better implemented in an interative fashion, at least in nonfunctional languages.
The basic idea is to move the top disk and the whole remainder. Moving that remainder is again done by moving the top disk and then moving what is left. With recursion, the functions are called in the right way such that the whole problem is solved in basically three lines:
move(from_stack, temp, items  1)
move(from_stack, to_stack, 1)
move(temp, to_stack, items  1)
There is a bit more to it as one has to catch the case of a single disk on a
stack. So have a look into
hanoi.py
.
There it is implemented, the Wikipedia article has a different implementation.
My version the outputs the following:
 4 3 2 1


 4 3 2
 1

 4 3
 1
 2
 4 3

 2 1
 4
 3
 2 1
 4 1
 3
 2
 4 1
 3 2

 4
 3 2 1


 3 2 1
 4

 3 2
 4 1
 2
 3
 4 1
 2 1
 3
 4
 2 1

 4 3
 2
 1
 4 3

 1
 4 3 2


 4 3 2 1
With recursion, one does not have to think about all the different cases that the three stacks could end up with, it just works out right.