Процесс может быть описан некоторым алгоритмом, называемым в данном случае рекурсивным. В нем выделяется два этапа выполнения:
1) «погружение» алгоритма в себя, т. е. применение определения «в обратную сторону», пока не будет найдено начальное определение, не являющееся рекурсивным;
2) последовательное построение от начального определения до определения с введенным в алгоритм значением.
Примеры рекурсивных алгоритмов, часто оформляемых в виде процедур и функций.
1. Наиболее распространенным рекурсивным определением является определение факториала (нерекурсивное вычисление факториала приведено в примере Р9): (a) 1! = 1, (b) n > 1, n: = n*(n - 1)!
На основе этого определения можно записать программу вычисления факториала, использующую рекурсивную функцию.
else F: = х * F (х - 1) {вызов для предыдущего определения}
end;{конец описания функции}
begin{начало главной программы}
readln(n);
Y: = F (n); {вызов функции в главной программе}
write (n, ‘! = ‘, Y)
end.{конец главной программы}
Выполним программу Р25 для n = 4. Рекурсивная функция будет работать следующим образом (при вызове функции значение n присваивается переменной х). Сначала осуществляется «погружение», работает оператор ветвиelse условного оператора:
1-й шаг: х = 4, х-1 = 3, выполняется промежуточное вычисление 4! = 4 * З!
2-й шаг: х = 3, х-1 = 2, выполняется промежуточное вычисление З! = 3 * 2!
3-й шаг: х = 2, х-1 = 1, выполняется промежуточное вычисление 2! = 2 * 1!
4-й шаг (последний): 1! = 1 по начальному определению, работает оператор F: = 1 ветвиthen условного оператора.
Следующий этап выполнения рекурсивного алгоритма — построение «прямого» определения, от начального до получения результата с исходными для алгоритма данными (числом 4). При этом осуществляется подстановка предыдущих вычислений (более поздних шагов) в более ранние:
5-й шаг: 2! = 2 * 1 = 2
6-й шаг: З! = 3 * 2 = 6
7-й шаг: 4! = 4 * 6 = 24 — получен результат, он возвращается в главную программу и присваивается переменной Y.
2. Вычисление степени с натуральным показателем можно определить рекурсивно:
(a) x 0 = 1
(b) k > 0: xk = x* xk - 1
Этому определению соответствует рекурсивная функция power (k, x). Программа имеет вид:
program Р26;
varу:real;n:Integer;
function power (k:integer;x:real): real;{описание рекурсивной функции} begin
if k=0
then power: = 1 {начальное определение}
else power: = x * power (k - 1, x) {рекурсивное определение}
end;{конец описания функции}
begin{начало главной программы}
write (‘ основание степени х = ‘);
readln(у);
write (‘показатель степени k = ‘);
readln(n);
write (‘х в степени k’, power(n, у)) {вызов функции и печать результата} end.{конец главной программы}
3. Вычисление чисел Фибоначчи. Итальянский математик Фибоначчи придумал последовательность натуральных чисел: 1, 1, 2, 3, 5, 8, 13, ... . Первые два члена последовательности равны единице, а каждый, начиная с третьего, равен сумме двух предыдущих. Для чисел Фибоначчи верно соотношение:
Fk = Fk + Fk-2
Рекурсивная функция получения значения n-го числа Фибоначчи имеет вид:
functionFib (n:integer): integer;
Begin
ifk<3
then Fib: = 1
else Fib: = Fib (n - 1) + Fib (n - 2)
end;
Для чисел Фибоначчи используется следующее рекурсивное определение:
(a)n= 1, n=2: fib(n) = 1
(b) n > 2: fib (n) = fib (n - 2) + fib (n - 1)
Для того чтобы определить fib (6), применяя данное рекурсивное определение, надо вычислить:
Количество действий в данных вычислениях с использованием рекурсивного определения чисел Фибоначчи резко возрастает, потому что это определение ссылается само на себя дважды. При вычислении факториала количество действий при выполнении программы с рекурсивной функцией и примера Е9 одинаково.
4. Рекурсивные алгоритмы могут быть оформлены и в виде процедур. Примером такой процедуры является решение задачи о Ханойских башнях.
Эта задача связана с легендой о том, что в одном из восточных храмов находится бронзовая плита с тремя алмазными стержнями. На один из них при сотворении мира нанизали 64 диска из чистого золота так, как показано на рисунке 7. Жрецы должны переносить диски с одного стержня на другой, следуя следующим законам:
1) диски можно перемещать только по одному;
2) нельзя класть больший диск на меньший.
Согласно легенде, когда все диски будут перенесены с одного стержня на другой, наступит конец света.
Решение этой задачи реализовано в виде рекурсивного алгоритма, который представляет собой инструкцию по перемещению дисков. Сформулируем задачу, присвоив имена стержням (А, В, С) и номера дискам (от 1 до n). Надо перенести диски со стержня А на стержень С, используя В как вспомогательный и
Рис. 7. Ханойские башни
следуя приведенным выше правилам переноса дисков.
Алгоритм на естественном языке имеет вид:
1) если n = 0, остановиться;
2) переместить верхние п - 1 дисков со стержня А на стержень В, используя стержень С как вспомогательный;
3) переместить оставшийся диск со стержня А на стержень С;
4) переместить п - 1 дисков со стержня В на стержень С, используя стержень А как вспомогательный.
В процедуре появляется новый тип данных —char, значение этого типа — один символ, заключенный в апострофы.
