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

Рекурсивные алгоритмы особенно подходят для задач, где обрабатываемые данные определяются в терминах рекурсии. Однако это не означает, что такое рекурсивное определение данных гарантирует бесспорность употребления для решения задачи рекурсивного алгоритма.

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

P º IF В THEN S; P, (6)

P º S; IF В THEN P. (7)

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

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

f_i = 1, 1, 2, 6, 24,120,... . (8)

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

f_i+1 = (i + 1)* f_i. (9)

Такое рекуррентное отношение предполагает рекурсивный алгоритм вычисления n-гофакториального числа. Если мы введем две переменные I и F, обозначающие i и f_i на i-м уровне рекурсии, то обнаружим, что для перехода к следующему числу последовательности (8) нужно проделать такие вычисления:

I := I+1; F := I * F, (10)

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

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

I := 0; F := 1; P. (11)

В принятых нами обозначениях первую строчку (11) можно переписать так:

PROCEDURE P(I: INTEGER, VAR F: INTEGER);

BEGIN

IF I < n THEN BEGIN I := I+1; F := I * F; P(I, F) END; (12)

END;

Однако более часто употребляется и полностью эквивалентная ей запись, где вместо процедуры Р используется функция. В этом случае переменная F становится излишней, а роль I явно выполняет параметр функции:

FUNCTION F (I: INTEGER): INTEGER;

BEGIN

IF I > 0 THEN F := I*F(I-1) ELSE F := 1; (13)

END;

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

I:=0; F:=1;

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

В общем случае программы, построенные по схемам (6) и (7), нужно переписывать, руководствуясь схемой:

P º [x:=x₀; WHILE B DO S]. (15)

Конечно, существуют и более сложные схемы рекурсий, которые можно и необходимо переводить в итеративную форму.

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