Одна із прадавніх легенд говорить: «У непрохідних джунглях недалеко від міста Ханоя є храм бога Брами. У ньому перебуває бронзова плита із трьома алмазними стрижнями. На один зі стрижнів бог при створенні миру нанизав 64 диски різних діаметрів із чистого золота. Найбільший диск лежить на бронзовій плиті, а інші утворюють піраміду, що зужується догори. Це вежа Брами. Працюючи день і ніч, жерці храму переносять диски з одного стрижня на інший, дотримуючись законів Брами:

1) диски можна переміщати з одного стрижня на іншій тільки по одному;

2) не можна класти більший диск на менший;

3) не можна відкладати диски убік, при переносі дисків з одного стрижня на інший можна використовувати проміжний третій стрижень, на якому диски повинні перебувати теж тільки у вигляді піраміди, що зужується догори.

Коли всі 64 диска будуть перенесені з одного стрижня на іншій, настане кінець світу».

Ця прадавня легенда покладена в основу завдання про Ханойську вежу: перемістити n дисків зі стрижня 1 на стрижень 3, використовуючи проміжний стрижень 2 і дотримуючи законів Брами.

Якщо вежа складається з одного диска, то він переноситься за один хід: 1->3.

Вежа із двох дисків переноситься за три ходи: 1—>2, 1->3, 2->3.

Для переносу вежі із трьох дисків буде потрібно вже сім ходів: 1->3, 1->2, 3->2, 1->3, 2->1, 2->3, 1->3. Зверніть увагу, за перші три ходи ми переносимо вежу із двох верхніх дисків на другий проміжний стрижень. Потім переносимо найбільший диск із першого стрижня на третій і ще раз проробляємо добре знайому нам операцію: переносимо вежу із двох дисків на третій диск.

Отже, щоб перенести вежу із чотирьох дисків з першого стрижня на третій, необхідно діяти за планом:

1) перенести вежу із трьох верхніх дисків з першого стрижня на другий (7 ходів);

2) найбільший диск перенести з першого стрижня на третій (1 хід);

3) перенести вежу із трьох дисків із другого стрижня на третій (7 ходів).

Усього на перенос буде потрібно 15 ходів.

Міркуючи аналогічним образом, порахуємо число ходів, необхідних для переносу вежі з п'яти дисків: 15 + 1 + 15 = 2 * 15+ 1 = 31.

Для вежі з 6 дисків одержуємо: 2 * 31 + 1 = 63 і т.д.

Розглянутий нами алгоритм рішення завдання «Ханойська вежа» має одну дивну властивість: у ході його виконання для вежі, що полягає з n кілець, ми використовуємо алгоритм для трохи більш простої ситуації — переносу вежі, що полягає з n - 1 кільця. У свою чергу, в алгоритмі для вежі з n - 1 кільця використовується цей же алгоритм для n - 2 кілець і т.д.