The Tower of Hanoi is a well-known puzzle where disks of different sizes are moved back and forth between three rods (A, B, and C). At the beginning, all disks are in position A. The aim is to bring all the disks into position B, whereby the rod C can also be used in between. The essential condition is that a larger disk must never lie on top of a smaller one.
In computer science textbooks, the Tower of Hanoi is often used as a standard example of recursive programming. The compexity of the associated algorithm increases exponentially with the number of disks, as the following formula shows:
n ... number of disks
m ... minimal number of moves