В теле процедур и функций могут быть записаны идентификаторы других процедур и функций, то есть из одной подпрограммы можно вызвать дру­гую подпрограмму. Но наиболее интересный случай таких вызовов - это когда подпрограмма вызывает саму себя. Этот приём программирования называется рекурсией.

Хорошим примером рекурсии в литературе могут служить докучные сказ­ки, которые находчивый русский народ придумал для того, чтобы изво­дить ими своих врагов, поскольку они никогда не заканчиваются (и те, и другие). Такую рекурсию называют бесконечной. В программах она вызы­вает «зависание» компьютера до тех пор, пока не будут полностью исчер­паны его ресурсы. Естественно, такое поведение приложения совершенно недопустимо, поэтому для рекурсивных подпрограмм необходимо преду­смотреть условие выхода из рекурсии. 

Для гуманизации интерфейса установим на форме компонент 1И: TSP|nEdlt (Палитра Samples), который будет ограничивать число повторений сказ­ки. После нажатия на кнопку btnPopСказочка, мы попадём в обработчик события: 

 procedure TForm1.btnPopClick(Sender: TObject); var n: integer; begin n:= speIter.Value; pop(n); listbox1.TopIndex:=listbox1.Items.Count-1; end; 

Здесь мы просто указываем программе, сколько раз хотим услышать эту душещипательную историю. Это и будет тот счётчик повторений, который избавит нас от бесконечной рекурсии.

А вот и сама сказочка:

 procedure pop(n: integer);  begin  if n <= 0 then exit;  Form1.listbox1.Items.Add( ’У попа была собака, он её любил,’); Form1.listbox1.Items.Add( ’Она съела кусок мяса, он её убил.’); Form1.listbox1.Items.Add( ’В землю закопал и надпись написал:’); Form1.listbox1.Items.Add( ’’); pop(n-1);  end; 

В первой строке как раз и находится обязательное условие, гарантирую­щее завершение сказочки. Как только параметр nстанет равным нулю, процедура закончится. Но до этого она будет напечатана 1 раз, а затем вы­зовет себя

 pop(n-1);  

для повторения сказки на 1 раз меньше. Таким образом, процедура будет вызвана 5 раз (если вы не изменили начальное значение):

 pop(4); pop(3); pop(2); pop(1); pop(0); 

На последнем вызове сработает первая строка, и страдания читателя сих милых строк закончатся. 

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

Перейдём теперь к несказочной рекурсии - к классическому примеру вы­числения факториала.

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

Здесь всё также начинается с задания количества повторов в окошечке Factorial, это как раз и будет то число, для которого мы будем вычислять факториал. Дополнительно засекаем время работы функции factorial, хотя на современных компьютерах это всегда будет 0. 

Чтобы расширить допустимые пределы для результата вычислений, вы­берем целый тип int64.

 //Рекурсивное вычисление факториала  procedure TForm1.btnFactorialClick(Sender: TObject); var   time,time0: single;   n: integer;   //k: longword;   k: int64;   s: string;   begin     time0:=GetTickCount(); //засечь начало   time:=time0;     n:= speFactorial.Value;   listbox1.items.add('Вычисляем факториал ’ + inttostr(n)); k:=factorial(n);   listbox1.items.add('Факториал ’ + inttostr(n) + ’ = ’ + int- tostr(k));     time0:=(GetTickCount()-time0)/1000;   str(time0:6:3,s);   listbox1.items.add(’Time ’ + s + ’ s’);    listbox1.items.add('');   listbox1.TopIndex:=listbox1.Items.Count-1; end;

А вот как просто рекурсивно вычисляется факториал - всего 2 строки кода:

function factorial (n: integer): int64; begin if n = 0 then factorial:= 1 else factorial:= factorial(n-1)*n;  end;

Сравните её с той функцией, что мы рассматривали ранее. Обратите вни­мание на первую строку, где проверяется условие завершения рекурсии!

Рекурсивные подпрограммы выглядят очень красиво, «профессионально», однако не стоит ими злоупотреблять - практически всегда можно решить задачу и без рекурсии (но не всегда это решение будет проще). С помощью рекурсии следует решать задачи, в которых требуется многократно вы­полнить сходные действия. При этом должно существовать нерекурсивное решение для самого простого из этих действий, которое и будет служить условием завершения рекурсии. Часто рекурсию используют для решения комбинаторных задач с полным или частичным перебором: обход лаби­ринта, расстановка ферзей, генерирование перестановок чисел, голово­ломка Ханойские башни.