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

Рекурсивные подпрограммы особенно удобно использовать для решения задачи, для которой уже есть внешняя спецификация. Но это совсем не означает, что лучший способ решения задачи -- прямое переписывание рекурсивных определений функций на язык Паскаль. На практике нам нужна не просто правильная программа. Программа должна быть достаточно эффективна, по крайней мере настолько, чтобы было возможным за разумное время получить результаты счета по программе на доступной ЭВМ. Например, в п. 2.3.1 приведены две спецификации функции возведения в степень, которым соответствуют следующие рекурсивные функции:

procedure Степ1 (X:real; N:integer):real;
begin if N=1 then Степ1:=X else Степ1:=Степ1(X,N-1)$*$X end end Степ1;

procedure Степ2 (X:real; N:integer):real;
begin
    if N = 1 then Степ2 := X
    elsif Odd(N) then Степ2(X,N-1)$*$X
    else Степ2 := Sqr(Степ2(X,N div 2))
    end
end Степ2;

вторая из которых заведомо является более эффективной, причем весьма существенно. Нетрудно увидеть, что обращение Степ1(Y,M) приводит к одновременному выполнению М экземпляров тела процедуры Степ1, а глубина рекурсии при выполнении Степ2(Y,M) составляет по порядку $\log_2 M$. Таким образом, по объему памяти, необходимой для выполнения подпрограммы, а также по времени ее выполнения (оценивается количествами операций умножения, сравнения и т.п.) подпрограмма Степ2 лучше подпрограммы Степ1 примерно в $M / \log_2 M$ раз (например, при M$\approx$ 1000 имеем $M / \log_2 M\approx$ 100).

Далее, не рекомендуется использование рекурсии, если есть возможность естественным образом выразить решение задачи при помощи циклов. Дело в том, что циклы на современных ЭВМ реализуются обычно более эффективно, чем вызовы подпрограмм, кроме того, заменяя рекурсию циклами, мы существенно экономим память, поскольку при каждом рекурсивном вызове подпрограммы должна выделяться дополнительная память для размещения ее локальных переменных. В п. 6.1.7 приведена функция ФАКТ для вычисления факториала. Совершенно ясно, что здесь рекурсию можно (и нужно!) заменить циклом -- см. функцию ФАКТ из п. 6.1.5. Вместе с тем последняя рекомендация совсем не означает, что всегда нужно избавляться от рекурсии любой ценой. Те алгоритмы, которые по своей природе трудно выразить с помощью циклов, следует представлять в виде рекурсивных подпрограмм.