Реализация рекурсии

Вычисление функции F можно представить как цепочку вызовов новых копий этой функции c передачей новых значений аргумента и возвратов значений функции в предыдущую копию.

n-1 n-2 n-3 0

n!

F(n) F(n-1) F(n-2) F(1)

Цепочка вызовов обрывается при передаче нуля в новую копию функции. Дви­жение в прямом направлении (развора­чива­ние рекурсии) сопро­вож­дается только вычислением условия и вызовом.

Значение функции вычисляется при сворачивании це­по­ч­ки вызовов.

Рекур­сивное обращение к проце­дуре (рекурсивный вызов функ­ции) можно представить как

• Построение в памяти компьютера новой копии этой процедуры;

• Передачу управления в эту новую копию (с новыми значениями параметров);

• Обработку (возможно – рекурсивную) данных в этой копии;

• Возврат в предыдущую копию (с прежними значе­ни­ями параметров)

Примеры рекурсивных и нерекурсивных описаний

Пример 3. Функция GCD(x, y) вычисляет наибольший общий делитель (НОД) двух натуральных чисел x и y. (Алгоритм Евклида)

Алгоритм Евклида, изучаемый в школьном курсе математики в средних классах, нахо­дит НОД двух чисел, вычитая из большего числа меньшее.

{итеративное описание}

Function GCD (x, y : Integer) : Integer ;

Begin

While x <> y do

If x < y

then y := y - x

else x := x - y ;

GCD := x

End;

{рекурсивное описание}

Function GCD (x, y : Integer) : Integer ;

Begin

If x <> y

Then If x < y

then GCD:= GCD(x, y - x)

else GCD := GCD(x - y, y)

Else GCD := x

End;

Рекурсивная версия следует из свойств НОД, выра­­жен­ных формулами - соотношениями:

x < y  НОД(x, y) = НОД(x, y - x)

x > y  НОД(x, y) = НОД(x - y, y)

НОД(x, x) = x;

Function GCD (x, y: Integer) : Integer ;

Begin

If (x <> 0)and(y <> 0)

Then GCD:= GCD(y mod x, x mod y)

else GCD := x + y

End;

Пример 4. Функция Pow(x, N) возводит положительное действительное число x в натуральную степень N. (Y = x^N )

{итеративный алгоритм }

Function Pow(x: Real; N: Integer):Real;

Var I: Integer; y: Real;

Begin

y := 1;

For i:=1 to N do y := y * x;

Pow := y

End;

{рекурсивный алгоритм}

Function Pow(x: Real; N: Integer) : Real;

Begin

Case N of

0: Pow := 1;

1: Pow := x

else

Pow := Sqr(Pow(x, N div 2))*Pow(x, N mod 2)

end

End;

Итеративный алгоритм вычисления степени x^N умножает y на x ровно N раз, начиная с y = 1. Для вычисления x^N алго­ритм выполняет N умножений.

Рекурсивный алгоритм: для вычисления x^N сначала предлагается вычис­лить x в половинной степени, а затем результат возвести в квадрат.

x⁰ = 1; x¹ = x;

N четно  x^N = (x^{N / 2} )²;

N нечетно  x^N = (x ^{(N-1) / 2} )² * x

В этой версии алгоритм выполнит не более log₂(N) возве­дений в квадрат и log₂(N) умножений - всего 2 log₂(N) действий.

С помощью рекурсии удалось просто описать эффек­тив­ный по времени (т.е. по количеству действий) алгоритм возведе­ния в степень.

Детали рекурсивных алгоритмов

Алгоритмы, использующие рекурсию, обязаны содержать процедуру (функцию), вызываемую рекурсивно.

Всю совокуп­ность переменных, используемых для описания рекурсив­ного алгоритма, можно разделить на 3 группы:

• глобальные переменные алгоритма;

• параметры рекурсивной процедуры (функции);

• локальные переменные этой процедуры (функции).

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

Локальные переменные могут изменить свои значения только в данной копии рекур­сивной процедуры. Значение локальной переменной, которое она имеет в момент рекурсивного вызова, не изменится и после возврата (выхода) из рекурсии.

Procedure E(N:Integer);