Рекурсия

В разделе 6.7 мы говорили о разработке алгоритмов и программ сверху вниз. При разработке программы часто исходную задачу сводят к более простым. Среди этих задач может оказаться и первоначальная задача в упрощенном виде. Рекурсия – это самовложение, при котором внутри некоторого объекта содержится подобный ему объект. В математике используются рекурсивные определения, в программировании – рекурсивные программы. В основе рекурсивного алгоритма лежит рекурсивное определение. Рекурсивным называется определение понятия через само это понятие.

Например, необходимо вычислить значение F= N! (факториал от N).

Можно сказать, что

N! = 1 * 2 * … * N при целом N > 0.

N! = 1 при N = 0,

Это определение использует итерацию (повторение) умножений и его можно назвать итеративным.

Можно дать другое определение факториала:

N! = (N – 1)! * N при целом N > 0.

N! = 1 при N = 0,

Здесь факториал от N выражается через само определяемое понятие – факториал от (N – 1), т. е. второе определение является рекурсивным.

Вычислим, например, 2! по второму определению:

2! = 2 * (2-1)! = 2*1! = 2 * 1 * (1-1)! = 2*1*0! = 2*1*1 = 2

Используем первое определение для вычисления факториала с помощью итеративного цикла. Фрагмент программы на языке Pascal:

…

Var I, N, F: Integer;

…

ReadLn (N);

F:=1;

for I:=1 to N do

F:= F * I;

…

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

Вычисление факториала на основе рекурсивного определения приведено в следующей функции.

{ Рекурсивное определение функции fakt(N) = N! }

function fakt (N: Integer): Integer;

begin

if N = 0 then

fakt:=1

else

fakt:= fakt(N-1) * N {рекурсивный вызов функции}

end;

Определение функции fakt содержит вызов этой же функции и поэтому является (прямо) рекурсивным.

Если некоторая программа A вызывает программу B, которая вызывает программу C, содержащую обращение к программе A, то эти три программы являются (косвенно) рекурсивными.

Рекурсивное определение и рекурсивная программа должны иметь хотя бы одну не рекурсивную ветку (в примере с факториалом это – вариант: k! = 1 при k = 0). Ее отсутствие приведет к бесконечному повторению рекурсивных вызовов.

Как реализуется рекурсия? После вызова любой подпрограммы в общих чертах происходит следующее:

1. в памяти размещаются значения входных параметров подпрограммы;

2. запоминается адрес возврата в вызывающую подпрограмму;

3. в памяти создается новый экземпляр внутренних переменных подпрограммы;

4. управление передается вызванной подпрограмме.

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

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

В некоторых языках, где этот механизм реализован не полностью, например, Basic, рекурсивные программы запрещены.

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

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

Задача. 6.18. Дано рекурсивное определение процедуры POWER (X, N, Y), которая возводит число X в целую степень N и возвращает результат в величине Y. Процедура имеет два входных параметра X и N, передаваемые по значению, и один выходной параметр Y, передаваемый по ссылке.

Procedure POWER (X: Real, N: Integer, Var Y: Real);

Begin

if N=0 then Y:=1

else begin

POWER (X, N-1, Y);

Y:= Y*X;

end;

end;

Проследим выполнение вызова POWER (5, 3, Y). Локальные данные процедуры – параметры X и N, для каждого вызова новые, поэтому указаны с индексом, равным номеру вызова процедуры. Стрелка -> означает вход в процедуру, а стрелка <- выход из процедуры.

Первый вызов процедуры для N =3

X₁ N₁ Y

-> POWER (5,3,Y) 5 3?

Второй вызов процедуры для N=2

X₂ N₂

-> POWER (5,2,Y) 5 3 5 2?

Третий вызов процедуры для N=1

X₃ N₃

-> POWER (5,1,Y) 5 3 5 2 5 1?

Четвертый вызов процедуры для N=0

X₄ N₄

-> POWER (5,0,Y) 5 3 5 2 5 1 5 0?

При N = 0 величина Y = 1, нового вызова процедуры нет. Начинается возврат, сначала из четвертого вызова. Результат четвертого вызова Y, равное 1, умножается на X и это становится результатом третьего вызова и так до первого вызова.

Y

<- POWER (5,0,Y) 5 3 5 2 5 1 1

<- POWER (5,1,Y) 5 3 5 2 1*5=5

<- POWER (5,2,Y) 5 3 5*5=25

<- POWER (5,3,Y) 25*5=125

Пояснения. Сначала глубина рекурсии растет. В каждом следующем вызове процедуры POWER параметр N уменьшается на единицу. Рекурсивные вызовы процедуры POWER выполняются до тех пор, пока N>0. При N=0 работает не рекурсивная ветка процедуры, величина Y принимает значение 1, и начинается возврат из процедур.

Задача 6.19. Дано определение функцииF() следующего вида:

Function(X: Integer): Integer;

Begin

If X=1 then F:=0

Else

If Odd(X) then F:= F(3*X + 1) +1

Else F:= F(X div 2)+2

End;

Найти значение функции F(26).