Рекурсивные процедуры и функции

 

Рекурсивным называется объект, который частично определяется через самого себя. Рекурсивные определения используются во многих областях науки и, особенно, в математике.

Рассмотрим функцию определения факториала (n!); факториал – это произведение первых n натуральных чисел. Такое произведение можно вычислить с помощью программы, использующей оператор цикла for. Однако, существует другое определение факториала, в котором используется рекуррентные формулы:

(1) 1!=1;

(2) для любого n>0, n!=n*(n-1)!

Определения, использующие рекуррентные формулы, называют рекурсивными определениями. Рекурсивные определения упрощают процесс вычислений. Например, в случае определения членов ряда Фибоначчи:

 

Рекурсивное определение значительно проще приведенной выше формулы и имеет следующий вид:

(1) F(1)=1;

(2) F(2)=1;

(3) Для любого n>2, F(n)=F(n-1)+F(n-2).

Рассмотрим рекурсивный алгоритм на примере накопления произведений. Пусть требуется написать программу, которая определяет произведение натуральных чисел от 1 до n:

P=n!=1*2*…*n.

Постановка задачи.

Входные данные:

n>0 – целое число.

Выходные данные:

P= n! – целое число.

Аномалии. n<0, в программе не рассматриваются.

Метод решения: для определения произведения использовать рекуррентные формулы:

1. 1!=1;

2. для любого n>0, n!=n*(n-1)!

Блок-схема рекурсивной функции fact для определения факториала представлена на рис 9.10, а блок-схема основной программы – на рис. 9.11.

 

 

		Рис. 9.10

Текст программы на языке Паскаль.

 

Program Exam10;

Var

Ch, Proiz: integer;

Function Fact(n: integer): integer;

Var R: integer;

Begin

If n>0 then Fact:=n*Fact(n-1)

Else Fact:=1;

End;

Begin

Writeln('Input Ch>0 :');

Readln(Ch);

If Ch>0 then

begin

Proiz := Fact(Ch);

Writeln('Ch','!=',Proiz)

end

Else Writeln('Error! Ch<0');

Write('PRESS ANY KEY!!!');

Readln;

End.

 

Результаты тестирования.

1. Исходные данные:

Ch=3

Ch!=1*2*3=6

Результаты, выданные программой.

Input Ch>0 :

Ch!=6

PRESS ANY KEY!

 

2. Исходные данные:

Ch=-3

Результат- сообщение «Error! Ch<0».

Результаты, выданные программой.

Input Ch>0 :

-3

Error! Ch<0

PRESS ANY KEY!!!

Рекурсивный процесс предполагает прямой ход или рекурсивный спуск и обратный ход или рекурсивный возврат.

Прямой ход.

При каждом рекурсивном обращении к функции создается новый экземпляр памяти всех локальных переменных и параметров этой функции, который запоминается в некоторой области памяти. Глубина рекурсии определяется количеством выполненных рекурсивных вызовов. Цепочка вызовов рекурсивных подпрограмм создает в памяти связанную последовательность областей памяти, организованных по принципу стека: доступной является область, размещенная последней. Прямой ход завершается тем вызовом подпрограммы, в котором истинно условие выполнения ее нерекурсивной части.

Рекурсивный процесс выполнения функции Fact для Ch=3 имеет глубину рекурсии, равную 3, как показано в таблице ниже.

Текущий уровень рекурсии	Рекурсивный спуск (прямой ход)	Рекурсивный возврат (обратный ход)
		Ch=3 Fact:=3*Fact(2-1)	Fact:=3*2(=6)
	Ch=2 Fact:=2*Fact(2-1)	Fact:=2*1(=2)
	Ch=1 Fact:=1	Ch=1 Fact:=1

 

 

Обратный ход начинается с выполнения нерекурсивной части подпрограммы; после этого область стека, относящаяся к данному вызову удаляется и выполняется возврат к предыдущему вызову и т. д. Обратный ход завершается возвратом значения в программу, вызывавшую рекурсивную функцию.

В рекурсивной процедуре или функции должно быть условие выполнения нерекурсивных операторов для обеспечения завершения рекурсии, иначе возможны бесконечные рекурсивные вызовы и аварийное завершение программы из-за переполнения доступной памяти для стека.

В языке Паскаль допускается использование рекурсивных процедур. Рассмотрим пример рекурсивной процедуры на примере процедуры определения наибольшего общего делителя двух целых чисел.