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

End

Else

Case N of

Begin

Begin

Begin

Begin

Begin

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

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

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

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

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

While x <> y do

If x < y

then y:= y - x

else x:= x - y;

GCD:= x

End;

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

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

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;

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;

y:= 1;

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

Pow:= y

End;

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

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

0: Pow:= 1;

1: Pow:= x

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

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);

Var x:Integer;

Дата добавления: 2014-01-06