Рекурсия , или подпрограмма, вызывающая саму себя

[@Hgpeu]

Рекурсия

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

При написании рекурсивных программ следует помнить, что при рекурсивном вызове процедурой самой себя или другой процедуры следует соблюдать определенные «правила предосторожности». Рекомендуется компилировать программу с директивой {$S+}. Эта директива включает проверку переполнения стека (области памяти, в которой хранится состояние вызывающей подпрограммы). Если в процессе выполнения программы происходит переполнение стека, вызов процедуры или функции, откомпилированной с опцией {$S+}, приводит к завершению работы программы, а на дисплей выдается сообщение об ошибке. Полезно также использовать директиву {$R+}, включающую проверку диапазона переменных. В начале каждой процедуры (функции), вызываемой рекурсивно, можно разместить строку

if keypressed then Halt

. В этом случае при зависании программы вместо перезагрузки будет достаточно нажать любую клавишу.

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

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

Рассмотрим классический пример: «необходимо найти факториал числа» (факториал: y=n! = 1*2*3*4*…*n)
1!=1
2!=1*2=1!*2
3!=1*2*3=2!*3
n!=(n-1)!*n

function f(n: longint): longint;
begin
  if n=1 then f:=1
  else f:=f(n-1)*n;
end;

[Some1]

Если вы не понимаете, но хотите знать, почему важно использовать директиву {$S+} (слежение за переполнением стека), то читайте тему "Как устроены переменные паскаля" в которой детально изложен принцип выделения памяти под переменные, объяснено, как используется стек, и для чего он нужен в процедурах или функциях (в том числе и рекурсивных)

[lamachok]

Цитата

@Hgpeu, 27.12.03, 04:24
также будет процедура, вызывающая другую процедуру, которая, в свою очередь, обращается к первой процедуре (косвенная рекурсия).

При этом нарушаются правила Паскаля,
т.к. вышестоящая подпрограмма не знает о существовании нижестоящей.
Для того, что бы всё работало тип-топ, надо использовать опережающее описание.
Например:

Цитата

Procedure b(i:integer);Forward;
Procedure a(j:integer);
begin
b(i)
end;
Procedure b(i:integer);
begin
a(j);
end;

P.S. если не нравится могу удалить
[Оставь, нравится %)]

Сообщение отредактировано: Song - 11.03.04, 16:43

[tserega]

В чем плюсы и минусы рекурсии?
Главный минус - тормозА. Часто рекурсивные процедуры и функции работают ОЧЕНЬ медленно.
Для примера: вычисление чисел Фиббоначчи.
F(0) = F(1) = 1, F(N) = F(N - 1) + F(N - 2), N >= 2
Очевидное рекурсивное решение:

Function Fib(N : Byte) : Longint;
Begin
 If (N = 0) Or (N = 1) Then Fib:=1 Else
 Fib:=Fib(N - 1) + Fib(N - 2);
End;

Вычисление Fib(20) занимает очень много времени, т.к. многие значения функции пересчитываются по многу раз. Построим "дерево" вычислений Fib(5).

                                Fib(5)
                Fib(4)                                    Fib(3)
    Fib(2)                 Fib(3)                  Fib(2)      Fib(1)
Fib(1) Fib(0)      Fib(2)          Fib(1)       Fib(1) Fib(0)
               Fib(1) Fib(0)

Можно заметить, что Fib(2) вычисляется 3 раза! Для вычисления Fib(5) потребовалось 16 рекурсивных вызовов. В общем случае число вызовов Fib(N) пропорционально 2^N.
Плюсы - легкое программирование рекурентных формул и алгоритмов.
Рассмотрим пример: сгенерировать все подмножества данного множества.
Пусть есть N предметов, каждый из которых можно взять, или не взять. Значит, число вариантов 2^N.
Решение может быть таким:

Var N : Longint; {Число предметов}
Procedure Solve(S : String; P : Longint); {S - текущий комплект, P - номер предмета,который рассматриваем}
Begin
 If (P > N) Then {если проверили все N предметов}
  Writeln(S) Else {выводим на экран: 0 - предмета нет, 1 - есть}
  Begin
   Solve(S + '1', P + 1); {можем взять очередной предмет}
   Solve(S + '0', P + 1); {а можем не взять}
  End;
End;
 
Begin
 N:=3;
 Solve('', 1);
End.

[KiRiK]

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

[Нет. Есть одна тема, там где "фиксные выражения" в ней есть серьёзный пример с деревьями. Но без описания.]