Рекурсивные определения и алгоритмы

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

Пример 1: Натуральные числа.
а) 0 есть натуральное число;
б) число, следующее за натуральным, есть натуральное число.

Пример 2: Факториал n!=1×2×3… n.
а) 0! = 1
б) при n>0 n! = n× (n-1)!

Очень важно то, что рекурсивное определение конечным высказыванием задает бесконечное множество объектов (скажем, бесконечное множество натуральных чисел).

В программировании рекурсивная процедура или функция вызывает САМУ СЕБЯ. В Паскале это разрешено:

FUNCTION fact(n:WORD):LONGINT;
BEGIN
IF n=0 THEN
fact := 1
ELSE
fact := n*fact(n-1)
END;

Как такое может быть? Как же реализованы вызовы процедурой самой себя? Дело в том, что при каждом рекурсивном вызове в памяти создается новый набор локальных переменных рекурсивной процедуры/функции (Рис. 16.1).

Рис. 16.1. Рекурсивные вызовы.

Если при каждом вызове в памяти образуется новый набор локальных переменных, а в цикле таких вызовов можно организовать тысячи, то, очевидно, что рекурсивные алгоритмы очень активно потребляют память. Если локальные переменные занимают хотя бы 100 байт, то уже на 656 итерации рекурсивного цикла их суммарный объем превысит 64Кб – максимальный размер сегмента памяти - и возникнет ошибка. Особенно опасно зацикливание рекурсии.