Рекурсия
Такой процесс, когда в процедуре происходит обращение к самой себе, называется рекурсией
(рекурсия - возврат). (Происходит от латинского recurreus - возвращающийся).
Теперь нам предстоит более подробно поговорить о рекурсиях.
Рекурсия - это такой способ организации подпрограммы, при котором в ходе выполнения она обращается сама к себе.
Приведем примеры, которые уже стали классическими, использования рекурсий в подпрограммах:
Пример 10. Вычисление факториала числа.
Ниже приведена программа вычисления факториала числа, в которой используется рекурсивная процедура fac:
Procedure fac(n : integer; var f : real);
begin
if (n = 0) or (n = 1) then f := 1
else
begin
fac(n - 1, f);
f := f*n
end
end;
Разберемся детально в работе этой процедуры. Для этого снова обратимся к математике.
Для вычисления факториала числа n, т.е. n! надо умножить последовательно n натуральных чисел от 1 до n:
Так, 4! будет равно:
Это прямой путь вычисления или итеративный.
Возможен и другой путь вычисления:
Именно на этом принципе основана работа приведенной процедуры.
Пусть введено в программу значение 4 для вычисления факториала 4! Как будет работать процедура?
После начала ее работы, будет выполнена проверка:
if (n = 0) or (n = 1) then
f := 1
Понятно, что 4 не равно 0 и не равно 1, значит будет выполняться оператор после else, т. е. fac(n - 1, f), а это означает, что снова будет вызвана также процедура, но значение n уменьшится на единицу и станет равным 3; затем снова будет выполнена проверка условия:
if
(n = 0) or (n = 1) then f := 1 и переход к вызову процедуры fac(n - 1, f).
Значение n
уменьшится на 1 и станет равным 2 и т.
д. до тех пор, пока n не станет равным 1, а значение f получит значение 1 ( надо заметить, что при всех предыдущих операциях значение f оставалось равным 0, а точнее говоря, неопределенным).
После этого, начнется обратный процесс, в котором будет выполняться команда: f := f*n. Он будет происходить так:
f := 1*4; f := 4*3; f := 12*2; f := 24*1.
Образно говоря, при первоначальном процессе, значения n от 4 до 1 "запоминаются" в стековую память "Паскаль-машины", а при следующем процессе, значения n "считываются" из стековой памяти “Паскаль-машины”
и умножаются на значения f.
Условно-схематически это можно изобразить так: значения n запоминаются в стек-память "Паскаль-машины":
|
4 |
|||
|
3 |
4 |
||
|
2 |
3 |
4 |
|
|
1 |
2 |
3 |
4 |
Обязательным элементом в описании всякого рекурсивного процесса является некоторое утверждение, определяющее условие завершения рекурсии; иногда его называют опорным условием рекурсии (или "якорем"). В нашем случае это условие:
if
(n = 0) or (n = 1) then f := 1.
В опорном условии может быть задано какое-то фиксированное значение, заведомо достигаемое в ходе рекурсивного вычисления и позволяющего организовать своевременную остановку процесса; применительно к вычислению факториала им будет равенство 1! = 1. Таким образом, любое рекурсивное определение всегда содержит два элемента: условие завершения и способ выражения одного шага решения посредством другого, более простого шага.
Для четкого понимания происходящих при этом процессов необходимо иметь в виду, что:
а) при каждом вызове процедуры создается новый экземпляр f;
б) все экземпляры f накапливаются во внутреннем стеке “Паскаль-машины” и
в) в любой момент обработке доступен только один, хронологически последний экземпляр переменной f, который
г) по завершению очередного рекурсивного вызова автоматически уничтожается).
Вывод
При каждом входе в рекурсивную подпрограмму ее локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком.
Программа
Program Problem10;
uses WinCrt;
var
n : integer;
f : real;
{---------------------------------------------------------------------------------------}
Procedure fac(n : integer; var f : real);
begin
if (n=0) or (n=1) then f := 1
else
begin
fac(n - 1, f);
f := f*n
end
end;
{---------------------------------------------------------------------------------------}
begin
write('Введите натуральное значение n '); readln(n);
fac(n, f);
writeln('Факториал числа ', n, ' равен ', f:12:0)
end.
Турбо-Паскаль 7 или 6 дает очень удобную возможность пошаговой трассировки программы и процедуру. Для этого достаточно последовательно нажимать клавишу F7 и вы сможете полностью убедиться в правильности наших соображений.
Рекурсивная форма организации подпрограммы обычно выглядит изящнее итерационной (последовательной) и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека.
Как избавиться от этой неприятности вы узнаете позже. Но стоит знать, что при зацикливании программы следует выйти из нее нажатием <Ctrl>+<Z>+<Enter> (<Ввод>) (для Турбо-Паскаля 7 или 6).
Еще примеры с использованием рекурсивных процедур.
Пример 11. Над цепью озер летела стая белых гусей. На каждом озере садилось половина гусей и еще полгуся, а остальные летели дальше. Все гуси сели на семи озерах. Сколько гусей было в стае?
Решение
Математически задача решается устно очень остроумным способом.
Пусть вместе со стаей белых гусей все время летит еще один, Серый гусь.
Если к некоторому озеру подлетит m белых гусей и Серый, то на этом озере садится
А теперь выполним, образно говоря, прямые рассуждения для решения задачи.
Обозначим через xk количество летящих белых гусей, когда впереди еще k озер. Тогда условие задачи записывается так:
Отсюда получаем для последовательности (xk) рекуррентное соотношение
Зная его, легко составить рекурсивную процедуру:
Procedure goose(x, k : integer);
begin
if k = 1 then writeln(x) else
goose(2*x + 1, k - 1)
end;
В процедуру вводятся всего две переменные: x - искомое число гусей; k - число озер. Процедура устроена с расчетом, что гуси уже пролетели все 7 озер, значит надо вводить значение для x - один (1), а для k - семь (7). В процедуре устроено, что число k уменьшается на 1 и тогда опорным условием ("якорем") завершения процедуры является условие равенства 1 значений k и после этого на экран надо выдать значение числа гусей:
if k = 1 then writeln(x)
Опорное условие может быть и другим, если первоначальным значением k будет 1, тогда при повторном обращении к процедуре значение k надо не уменьшать, а увеличивать на 1 (k + 1), опорным условием, в этом случае, будет k = 7.
Ниже приводится законченная программа решения этой задачи:
Program Problem11;
uses WinCrt;
var
k : integer;
{----------------------------------------------------------------------------------------}
Procedure goose(x, k : integer);
begin
if k = 1 then write(x) else
goose(2*x + 1, k - 1)
end;
{----------------------------------------------------------------------------------------}
begin
write('Введите число озер '); readln(k);
write('В стае было ');
goose(1, k);
writeln(' гусей')
end.
Придерживаясь подобных соображений, решите следующую задачу.
