This is a real beauty. In this case, without recursion, you have to use something like stack to rememeber all the steps you went through, and for an average person, it wold take you quite some time to make the stack right, when to push, when to pop...

With recursion, the REAL code is only about 4 or 5 lines long.

This could even be viewed as sort of AI program, but the solution is definite.