Tower of Hanoi

This problem might be the most famous example for teaching Recursion, and here is a simple example in Python. Advertisements