Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




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 = xN )

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

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;

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

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

x0 = 1; x1 = x;

N четно à xN = (xN / 2)2;

N нечетно à xN = (x (N-1) / 2)2 * x

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

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

 

 

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

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

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

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

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

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

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

Procedure E(N:Integer);

Var x:Integer;




Поделиться с друзьями:


Дата добавления: 2014-01-06; Просмотров: 328; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.007 сек.