Рекурсивные методы построения алгоритмов
Определение 6. Рекурсия – способ организации вычислительного процесса, при котором функция в ходе выполнения составляющих ее операторов обращается сама к себе.[7]
Использование рекурсии сокращает программу, в этом ее преимущество перед использованием итерационных циклов, но при выполнении может вызвать переполнение оперативной памяти компьютера.
Вид рекурсивной процедуры:
Рассмотрим типовой пример задачи вычисления факториала числа.
На рис. 13 показаны прямой и обратный ход рекурсии. [6] В любой рекурсивной подпрограмме обязательно должна быть не рекурсивная ветвь:
Пусть переменной a присваивается значение 5!:
Рис. 13. Прямой и обратный ход рекурсии.
Рассмотрим некоторые примеры использования рекурсии.[6]
1. Сложение двух чисел a + b. Рекурсивное определение операции сложения двух чисел:
a + b = 
2. Каждое число Фибоначчи равно сумме двух предыдущих чисел при условии, что первые два равны 1 (1, 1, 2, 3, 5, 8, 13, 21,…).В общем виде n-e число Фибоначчи можно определить так:
Ф(n)= 
3. «Ханойские башни». В конце XIX века в Европе появилась игра под названием «Ханойские башни». Реквизит игры состоит из 3 игл, на которых размещается башня из колец. Цель игры – перенести башню с левой иглы (1) на правую (3), причем за один раз можно перенести только одно кольцо. Кроме того, запрещается помещать большее кольцо над меньшим.
|
|
|
Программа, которая печатает последовательность переноса колец посредством рекурсивной процедуры, представлена в Приложении 1, Hanoy.pas.
Данная задача своим происхождением обязана легенде, в которой рассказывается, что в большом храме Бенареса на бронзовой плите установлены три алмазных стержня, на один из которых бог нанизал во время сотворение мира 64 золотых диска. С тех пор день и ночь монахи, сменяя друг друга каждую секунду, перекладывают по одному диску согласно описанным выше правилам. Конец мира наступит тогда, когда все 64 диска будут перемещены, на что потребуется чуть больше 58 млрд. лет.
Дата добавления: 2016-01-03; просмотров: 14; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!