Рекурсия

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

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

Пример.

Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

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

Program Arsac;

Var first: word;

Procedure posledov (i: word);

Begin

Writeln (i);

If i=1 then exit;

If odd(i) then posledov (3*i+1) else posledov (i div 2);

End;

Begin

Write (‘введите первое значение’); readln (first);

Posledov (first);

Readln;

End.

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

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

Пример.

N! = (N-1)!*N, если N=0, то N!= 1

Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через него же, другая часть – через иные понятия.

Пример.

2ⁿ= 2^n-1*2, если n=0, то 2ⁿ= 1

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

Заметим, что при косвенном обращении все процедуры в цепочке – рекурсивные.

Все сказанное о процедурах целиком относится и к функциям.

Пример рекурсивной функции вычисления факториала:

Function factorial(N: integer): longint;

Begin

If N= 0 then

Factorial:= 1

Else Factorial:= factorial(N-1) * N

End;

Рекурсия изнутри

Это может показаться удивительным, но самовызов процедуры ничем не отличается от вызова другой процедуры. Что происходит, если одна процедура вызывает другую? В общих чертах следующее:

1) в памяти размещаются параметры, передаваемые процедуре (но не параметры-переменные!);

2) в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;

3) запоминается адрес возврата в вызывающую процедуру;

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

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

Пусть рекурсивная процедура Power(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). Стрелка «®» означает вход в процедуру, стрелка «» означает выход из нее.

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