Математична модель. 
Задача про Ханойські вежі

Математичною моделлю даної задачі є рекурентне співвідношення.

Рекурентні співвідношення мають принципове значення в аналізі алгоритмів. Якщо алгоритм влаштований так, що він розбивається на декілька менших підзадач, то можна описати час його роботи з допомогою рекурентного співвідношення.

" Рекурентний" означає «зворотний». Справді, метод рекурентних співвідношень, дозволяє знаходити значення деякої функції для заданої величини аргументу через менші значення аргументів. Стосовно комбінаторики цей метод дає можливість знаходити розв’язок комбінаторної задачі для n предметів через розв’язок аналогічної задачі з меншим числом предметів за допомогою деякого співвідношення, яке називається рекурентним співвідношенням. Метод рекурентних співвідношень добре відомий з курсу шкільної математики, де він застосовувався при визначенні сум арифметичної і геометричної прогресій та при визначенні n-го члена цих прогресій.

Прикладами рекурентних співвідношень є:

Ряд чисел Фібоначчі.

Біном Н’ютона.

Алгоритм реалізації задачі

При побудові алгоритму використовується підхід «розділяй і володарюй». Ідея полягає в наступному:

завдання розбивається на кілька підзадач меншого розміру;

вирішуються ці підзадачі;

рішення підзадач комбінуються, й виходить рішення вихідної задачі.

Як правило, завдання вирішуються безпосередньо, або за допомогою рекурсивного виклику.

Алгоритм називається рекурсивним, якщо при вирішенні деякої задачі він викликає сам себе для вирішення підзадачі.

Для того, щоб перекласти всю піраміду з дисків, треба спочатку перекласти все, що вище найбільшого диска, з першого на допоміжний стрижень, потім перекласти цей найбільший диск з першого на третій стрижень, а потім перекласти залишилася піраміду з другого на третій стрижень, користуючись допоміжним стрижнем.