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

При написании рекурсивных программ следует помнить, что при рекурсивном вызове процедурой самой себя или другой процедуры следует соблюдать определенные «правила предосторожности».
Рекомендуется компилировать программу с директивой {$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;

В чем плюсы и минусы рекурсии? Главный минус - тормозА. Часто рекурсивные процедуры и функции работают ОЧЕНЬ медленно. Для примера: вычисление чисел Фиббоначчи. 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.