4. 5. Когда рекурсию использовать не нужно

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

Программы, в которых следует избегать алгоритмической ре­курсии, можно охарактеризовать некоторой схемой, отражающей их строение (специфично, что тут есть единственное обращение к Р в конце или начале всей конструкции):

Р≡ IF В THEN (S; Р), 3.6

Р ≡ (S; IF В THEN Р). 3.7

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

Например: вычисления факториала

i =0,1,2,3,4,5,….,

f_i=1,1,2,6,24,120,…. 3.8

Первое из чисел определяется явно f_о = 1, а последующие опре­деляются рекурсивным образом с помощью предшествующего числа:

f_i+1= (i+1)* f_{i 3.9}

Такое рекуррентное отношение предполагает рекурсивный алго­ритм вычисления n-го факториального числа.

Если мы введем две переменные I и F, обозначающие i и f_i; на i-м уровне рекурсии, то для перехода к следующему числу последовательности нужно проделать такие вычисления:

I := I+1; F: I*F 3.10

и, подставляя (3.10) вместо S в (3.6), получаем рекурсивную программу:

Р≡ IF I<n THEN I:= I+1; F: = I*F; P END; 3.11

В первую строчку (3.11) можно переписать так:

FUNCTION P;

BEGIN

IF I < n THEN BEGIN I := I+1; F := I*F; P END

END; {P}

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

В этом случае переменная F становится излишней, а роль I явно выполняет параметр процедуры:

FUNCTION F (I: INTEGER): INTEGER; BEGIN IF I > 0 THEN F := I*F (I-l)

ELSE F := 1

END; {F}

Теперь уже ясно, что в рекурсия крайне просто заменяется итерацией. Это проделано в такой программе:

I := 0; F :=1;

WHILE I < n DO BEGIN I := I+1; F := I*F END;

Программы, построенные по схемам (3.6) и (3.7), нужно переписывать, руководствуясь схемой:

Р≡ [х: =х₀ WHILE В DO S]. (3.15)

Следовательно, следует избегать рекурсий там, где есть оче­видное итерационное решение. Однако это не означает, что от рекурсий следует избавляться любой ценой.

Существует много хороших примеров применения рекурсии,

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

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

Алгоритмы, рекурсив­ные по своей природе, а не итеративные, нужно формулировать как рекурсивные процедуры.