posted 12 years ago
One problem that's interesting to solve recursively is the Towers of Hanoi puzzle. You have three pegs, and one of them holds a tower made out of discs. Each disc is larger than the one on top of it.
The puzzle is to move the entire tower from one peg to another peg. You can only take one disc at a time, and you may never place a large disc on top of a smaller one.
The key to solving the problem recursively is to realize that you *somehow* need to move the entire stack of discs except the bottom one to a free peg, move the bottom disc to the last peg, and then move the stack back on top of the bottom disc.