10-2.9
Рекурсия Паскаль
Подпрограммы в Паскале могут обращаться сами к себе. Такое обращение называется рекурсией.
Для того чтобы такое обращение не было бесконечным, в тексте подпрограммы должно быть условие, по достижению которого дальнейшее обращение к подпрограмме не происходит.
Пример.
Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».
Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.
Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.
Применение рекурсии позволило решить задачу без использования циклов, как в основной программе, так и в процедуре.
Пример программы с использованием рекурсии
Program Arsac;
Var first: word;
Procedure posledov (i: word);
Begin
Writeln (i);
If i=1 then exit;
If odd(i) then posledov(3*i+1) else posledov(i div 2);
End;
Begin
Write (' введите первое значение '); readln (first);
Posledov (first);
End.
Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме. Например, для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.
Алгоритм, который является своей собственной частью, называется рекурсивным. Часто в основе такого алгоритма лежит рекурсивное определение.
Пример рекурсивного алгоритма
N! = ( N-1)!* N, если N=0, то N!= 1
Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через него же, другая часть – через иные понятия.
Пример рекурсивного алгоритма
2n= 2 n-1*2, если n=0, то 2 n= 1
Процедура является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие процедуры).
Заметим, что при косвенном обращении все процедуры в цепочке – рекурсивные.
Все сказанное о процедурах целиком относится и к функциям.
Пример рекурсивной функции вычисления факториала
Function factorial(N: integer) : longint;
Begin
If N= 0 then
Factorial := 1
Else Factorial := factorial(N-1) * N
End;
Рекурсия изнутри
Это может показаться удивительным, но самовызов процедуры ничем не отличается от вызова другой процедуры. Что происходит, если одна процедура вызывает другую? В общих чертах следующее:
в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные!);
в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;
запоминается адрес возврата в вызывающую процедуру;
управление передается вызванной процедуре.
Если процедуру вызвать повторно из другой процедуры или из нее самой, будет выполняться тот же код, но работать он будет с другими значениями параметров и внутренних переменных. Это и дает возможность рекурсии.
Пусть рекурсивная процедура Power( X, N, Y) возводит число X в степень N и возвращает результат Y .
Пример рекурсивной процедуры, возводящей число в степень
Procedure Power (X: real; N: integer; var Y: real);
Begin
If N=0 then
Y:= 1
Else Begin Power(X, N-1,Y);
Y:= Y*X;
End ;
End ;
Проследим за состоянием памяти в процессе выполнения вызова данной процедуры Power(5,3, Y). Стрелка «->» означает вход в процедуру, стрелка «<-» означает выход из нее.
Число копий переменных, одновременно находящихся в памяти, называется глубиной рекурсии. Как видно из примера, сначала она растет, а затем сокращается.
Подведем итог
рекурсивной называется такая процедура или функция, которая вызывает сама себя;
для завершения процесса рекурсии в алгоритме рекурсивной функции (процедуры) обязательно должно быть условие, обеспечивающее непосредственное завершение функции (процедуры).
Напишем программу вычисления функции, заданной следующим образом:
F(1)=1; F(2n)=F(n); F(2n+1)=F(n)+F(n+1)
Решение: из определения видно, что вычисление функции от аргумента, сводится к вычислению этой же функции от меньшего аргумента, и процесс уменьшения аргумента продолжается до тех пор, пока в качестве аргумента не получится единица. Значение функции от единицы определено.
Таким образом, работа алгоритма будет состоять из некоторого количества шагов, на каждом из которых будут выполняться два действия:
Определение четности или нечетности аргумента. От этого зависит выбор формулы вычислений;
Выполнение вычислений. Фактически это будет сводиться к определению нового аргумента функции.
Пример рекурсивной программы вычисления функции
Program primer;
Uses crt;
Var
N, a: integer;
Function f(n:integer):integer;
Begin
If n =1 then
f :=1 {условие завершения рекурсии}
Else
Begin
If odd ( n ){проверка на нечетность числа}
then begin
n:= n div 2;
f:=f(n)+f(n+1)
end
else begin
n:= n div 2;
f:=f(n)
end;
end ;
end ;
begin {начало основной программы}
clrscr;
write(' Введите число – ');
readln(n);
a:=f(n);
write(' результат – ', a);
end.