На этом шаге мы приведем общие сведения о рекурсии.

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

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

    Рассмотрим функцию факториала n!. Как правило, ее определяют как произведение первых n целых чисел: n! = 1*2*3*...*n.

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

program Factorial;
var
  Fact : Longint;
  n, i : Integer;
begin
  Write ('Введите число n: ') ;
  Readln ( n ) ;
  Fact := 1;
  for i:= 1 to n do Fact := Fact * i;
  Writeln ('Факториал  n! = ', Fact);
end.

    Однако существует также другое определение факториала, в котором используется рекуррентная формула и которое имеет такой вид:

    (1) 0!   = 1
    (2) для  любого n > 0 n! = n * (n - 1)!

    Определения с помощью рекуррентных формул иногда называют рекурсивными определениями. Если для факториала первое (итеративное) определение может показаться проще, то для чисел Фибоначчи рекурсивное определение:

    (1)  F(1) = 1,
    (2)  F(2) = 1,
    (3)  для любого n > 2 F(n) = F(n-1) + F(n-2)

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

program Factorial; 
var
  n : Integer;
function Fact ( i : Integer ): Longint; 
begin
  if i = 1  then  Fact := 1
  else Fact := i * Fact (i-1) 
end;
begin
  Write  ('Введите число n: ') ;
  Readln (n);
  Writeln ('Факториал  n!  = ',   Fact(n)); 
end.

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

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

    Например, следующая процедура будет бесконечно печатать известные всем строки:

program  EndLess1;
procedure PopeAndDog1; 
begin
  Writeln('У попа была собака, он ее любил.'); 
  Writeln('Она  съела  кусок мяса, он  ее  убил,'); 
  Writeln('похоронил  и  надпись  написал:'); 
  PopeAndDog1 
end; 
begin
  PopeAndDog1 
end.

    Однако если оператор вызова процедуры поставить перед выводом текста, как показано ниже:

program EndLess2;
procedure PopeAndDog2; 
begin
  PopeAndDog2;
  Writeln('y попа была собака, он ее любил.'); 
  Writeln('Oнa съела кусок мяса, он ее убил,'); 
  Writeln('похоронил и надпись написал:'); 
end; 
begin
  PopeAndDog2 
end.

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

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

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

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

    Дадим некоторые определения, имеющие отношение к рекурсии.

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

    Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.

    На следующем шаге мы рассмотрим формы рекурсивных процедур.

Предыдущий шаг Содержание Следующий шаг