Ни одно рассмотрение рекурсии не было бы полным без рассмотрения старинной задачи о ханойских башнях.
Постановка задачи:
Даны три столбика – A, B, C. На столбике A один на другом находятся n дисков разного диаметра, пронумерованные сверху вниз. Причем они располагаются так, что каждый меньший диск находится на большем. Требуется переместить эти n дисков на столбик C, сохранив их взаиморасположение. Столбик B разрешается использовать как вспомогательный. При решении за один шаг допускается перемещать только один из верхних дисков какого-либо столбика. Кроме того, больший диск никогда не разрешается класть на диск меньшего диаметра.
Для определения подхода к решению поставленной задачи рассмотрим общий случай. Если мы сможем сформулировать решение для n дисков в терминах решения для n-1диска, то поставленная проблема была бы решена, поскольку задачу для n-1диска можно будет, в свою очередь, решить в терминах n-2дисков и так далее до тривиального случая одного диска. А для случая одного диска (n=1) решение получается элементарным. Нужно просто переместить один-единственный диск со столбика A на столбик C.
Таким образом, если сформулировать решение для nдисков в терминах n-1диска, то мы фактически получим алгоритм рекурсивной функции, с помощью которой можно легко достичь цели поставленной задачи. Рассмотрим словесное описание такого алгоритма.
if (n==1)
Переместить этот единственный диск со столбика A на столбик C и остановиться ;
Else
