Рекурсия

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

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

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

Таким образом, любая рекурсия обязательно должна содержать два условия:

1) условие окончания рекурсии (опорное условие рекурсии или “якорь”), в котором задается какое-то фиксированное значение, заведомо достигаемое в ходе рекурсивного вычисления и позволяющее организовать своевременную остановку вычислительного процесса. Выполнение этого условия не должно повлечь за собой нового рекурсивного вызова.

2) вычисление значения с помощью самовызова функции (рекурсивный вызов).

Задача 1. Напишите итерационную и рекурсивную функции вычисления факториала.

Решение. Итерационное вычисление факториала осуществляется следующим образом: n! = 1·2·3·...·n, что осуществляется путем умножения передыдущего значения факториала на i.

function factorial (n: integer): real;

var f: real;

i: integer;

begin

if (n = 0) or (n = 1) then factorial := 1

else

begin f := 1;

for i := 2 to n do

f := f * i;

factorial := f

end;

end;

Рекурсивное определение факториала:

В первой строке определения явно указано, как вычислить факториал, если аргумент равен нулю или единице. В любом другом случае для вычисления n! необходимо вычислить предыдущее значение (n-1)! и умножить его на n. Уменьшающееся значение гарантирует, что в конце концов возникнет необходимость найти 1! или 0!, которые вычисляются непосредственно.

function factorial (n: integer): real;

{рекурсивное вычисление факториала}

var f: real;

i: integer;

begin

if (n = 0) or (n = 1) then factorial := 1

else factorial := factorial (n - 1) * n;

end;

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

Активизируется предыдущая копия рекурсивного алгоритма, становятся доступными ее переменные. Пусть необходимо вычислить 4! Основной алгоритм: вводится n=4, вызов factоrial(4). Основной алгоритм приостанавливается, вызывается и работает factorial(4): 4<>1 и 4 <> 0, поэтому factorial:=factorial(3)*4. Работа функции приостанавливается, вызывается и работает factorial(3): 3<>1 и 3<>0, поэтому factorial:=factorial(2)*3. Заметьте, что в данный момент в памяти компьютера две копии функции factorial. Вызывается и работает factorial(2): 2<>1 и 2<>0, поэтому factorial:=factorial(1)*2. В памяти компьютера уже три копии функции factorial и вызывается четвертая. Вызывается и работает factorial(1): 1=1, поэтому factorial(1)=1.

Работа этой функции завершена, продолжает работу factorial(2). factorial(2):=factorial(1)*2 =1*2=2. Работа этой функции также завершена и продолжает работу функция factorial(3). factorial(3):=factorial(2)*3=2*3=6. Завершается работа и этой функции и продолжает работу функция factorial(4). factorial (4):=factorial(3)*4=6*4=24. Значение функции при n=4 равно 24.

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

Упражнение. Напишите рекурсивную функцию вычисления n-ого числа Фибоначчи.