Tower of Hanoi

A puzzle in which disks of different sizes are moved among three pegs, one at a time, without placing a larger disk on a smaller one. Its recursive solution requires at least 2ⁿ − 1 moves for n disks.

Recursion: A method of defining or solving a problem by reducing it to smaller instances of the same problem. The optimal solution moves a smaller stack aside, moves the largest disk, then solves another smaller instance.
Mathematical puzzle: A problem designed to reveal mathematical structure through a constrained challenge. The puzzle turns a simple physical rule into a problem about recursive structure and optimality.
Computer science education: The teaching and study of computing concepts, methods, and systems. The puzzle gives beginners a concrete way to trace recursive calls and termination.
Édouard Lucas: A French mathematician known for work in number theory and recreational mathematics. Lucas introduced the puzzle in his 1883 book on mathematical recreations.
Mathematical induction: A proof technique that establishes a base case and shows each case follows from its predecessor. Induction proves the recurrence gives the minimum number of moves for every disk count.
Greedy algorithm: An algorithm that repeatedly makes a locally optimal choice at each step. The optimal sequence can be generated by choosing the only legal move that preserves progress.
Algorithm analysis: The study of an algorithm’s resource use as a function of input size. Its exact move count makes exponential running time easy to derive and compare.
Récréations mathématiques: An 1882–1894 multivolume work by Édouard Lucas on mathematical recreations. Its 1883 volume presented the Tower of Hanoi to a broad mathematical audience.
Recurrence relation: An equation defining a sequence in terms of one or more earlier terms. The minimum move count satisfies T(n) = 2T(n − 1) + 1.
Minimum number of moves: The least number of operations needed to reach a specified goal under given rules. For n disks, the puzzle’s minimum is 2ⁿ − 1, attained by its recursive strategy.

Linked from 4 pages