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.