Описание слайда:
Рекурсия в языке C++ Примером задачи, где оправдано использование рекурсии, может служить решение задачи о Ханойских башнях. Эта задача формулируется следующим образом: имеется три стержня. На одном из них находятся диски, разных размеров, сужающиеся к верху (пирамида). Требуется перенести эти диски на другой стержень, используя только один, вспомогательный стержень. При этом за один раз можно перенести только один диск, а больший по размеру диск не допустимо ставить на диск меньшего размера Доказательство решения этой задачи основано на использовании индукционного метода, из которого непосредственно следует алгоритм, основанный на использовании рекурсивных функций. Так, для случая одного диска решение, очевидно, он просто перекладывается с исходного стержня на заданный. Для случая из двух дисков сначала верхний диск перекладывается на вспомогательный стержень, а затем нижний диск с исходного стержня и верхний со вспомогательного стержня перекладываются на заданный. Аналогично, для случая N дисков, сначала N-1 дисков при соблюдении правил перестановки перемещаются на вспомогательный стержень, а затем на заданный стержень переносится нижний диск (он нашёл своё место). Далее, учитывая, что последний диск, перемещённый на заданный стержень, никак не мешает, поскольку он больше всех остальных, задача решается аналогично. Исключение состоит в том, что N-1 диск, из оставшихся, перемещаются на вспомогательный, который ранее был исходным, используя в качестве промежуточного заданный, а последний из оставшихся снова перемещается на заданный стержень. Таким образом, после двух циклов перестановок, мы приходим к исходной ситуации использования стержней, но количество дисков, которых необходимо переставить меньше на два диска и т.д.. Процесс рекурсии останавливается, когда остаётся только один диск, который перемещается на заданный. Доказано, что для n дисков минимальное число необходимых перемещений равно 2^n-1.
