Wieża Hanoi to matematyczna łamigłówka, w której mamy trzy pręty ( A , B , I C ) I N dyski. Początkowo wszystkie krążki ułożone są w stos o malejącą wartość średnicy tzn. najmniejszy krążek jest umieszczony na górze i leżą na pręcie A . Celem łamigłówki jest przeniesienie całego stosu na inny pręt (tutaj rozważany C ), przestrzegając następujących prostych zasad:

• Jednocześnie można przenosić tylko jeden dysk.
• Każdy ruch polega na wzięciu górnego dysku z jednego ze stosów i umieszczeniu go na wierzchu innego stosu, tzn. dysk można przenieść tylko wtedy, gdy jest to dysk położony najwyżej na stosie.
• Żaden dysk nie może być umieszczony na mniejszym dysku.

Przykłady:

Wejście : 2
Wyjście: Dysk 1 został przeniesiony z A do B
Dysk 2 został przeniesiony z A do C
Dysk 1 został przeniesiony z B do C

Wejście: 3
Wyjście: Dysk 1 został przeniesiony z A do C
Dysk 2 został przeniesiony z A do B
Dysk 1 został przeniesiony z C do B
Dysk 3 został przeniesiony z A do C
Dysk 1 został przeniesiony z B do A
Dysk 2 został przeniesiony z B do C
Dysk 1 został przeniesiony z A do C

Poniższy film pokazuje rozwiązanie Wieża Hanoi dla wejścia (N) = 3 –

Quiz na temat rekurencji