20 Дайте определение рекуррентным выражениям. Дайте определение понятию рекурсия. Назовите Достоинства и недостатки рекурсивных программ. Приведите примеры рекурсивных процедур и функций.

Рекуррентность - Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.

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

Косвенная рекурсия – происходит тогда, когда процедура А вызывает процедуру В, а та в свою очередь вызывает процедуру А. Длинна таких цепочек может быть произвольной, но нужно следить за тем, что бы это обращение не зависало в постоянном цикле.

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

Любое рекурсивное определение функции можно заменить нерекурсивным. Точно

также и любой рекурсивный алгоритм можно заменить нерекурсивным. Так для вычисления

n! нерекурсивная функция будет описана следующим образом:

FUNCTION FACT (N: INTEGER): INTEGER;

VAR K,I: INTEGER;

BEGIN

K:=1;

FOR I:=1 TO N DO K:=K*I;

FACT:=K;

END;

Рекурсивность – это не свойство функции, а свойство ее описания. Какое же из описаний

лучше?

В общем случае рекурсивное описание короче и нагляднее, но требует больших затрат

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

дублирования локализованных в процедуре переменных). Чему отдать предпочтение –

следует решать в конкретном случае.

Каждый рекурсивный алгоритм нужно оценивать с точки зрения времени работы. Если

сам алгоритм даже при нерекурсивном описании содержит много действий, то в нем

относительное увеличение времени за счет рекурсии будет небольшим.

Если в алгоритме мало действий, то доля дополнительных команд может оказаться

слишком большой. Например, в алгоритме для n! рекурсивная процедура гораздо медленнее,

поэтому целесообразнее использовать его нерекурсивную форму, а именно – итеративную

(рекуррентную).

Поэтому вывод можно сделать следующий. Если задача имеет очевидное итеративное

решение, то рекурсии следует избегать. Однако это не значит, что от рекурсии нужно

избавляться всегда и любой ценой. Для алгоритма Хоара, например, потери во времени на

практике являются небольшими. Многие сложные алгоритмы описываются в рекурсивной

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

Пример:

Program Factorial;

Var F,N:integer;

Procedure FACT(N:integer; Var F:integer);

begin

IF N=0 THEN F:=1ELSE

begin

FACT(N-1,F); F:=N*F

end

end;

Begin

Write('Введите число= '); Readln(N);

FACT(N,F);

Writeln(F);

Readln

End