Сегодня мы продолжим разговор о классических методах программирования. В этой статье попытаемся обсудить такую технологию построения алгоритмов как рекурсия. Некоторые уже наверняка сталкивались с этим понятием, но, испуганные непонятными кусками кода или непривычностью идеи, поспешили забыть все увиденное и услышанное, надеясь вернуться к этому вопросу позже, и чем позже - тем лучше. Не спешите отложить эту статью, потому как, во-первых, рекурсия - это ДЕЙСТВИТЕЛЬНО просто, во-вторых, рекурсия относится к той группе методов, не зная которых, грамотно программировать НЕВОЗМОЖНО, и чем дольше вы прячетесь от нее, тем хуже.

Итак, не откладывая в долгий ящик, дадим наше первое рекурсивное определение. Мы опишем, используя рекурсию, функцию факториал (напомню, N!=1·2·...·N). Пример выбран не случайно - именно математики придумали рекурсию, а использовалась она для описания числовых последовательностей, следующие значения которых можно найти по предыдущим (такие последовательности называют рекуррентными).

Рекурсивное определение факториала:

1. 0! = 1

2. N!=N·(N-1)!

Итак, дело сделано. Теперь осталось выяснить, что обозначает приведенная запись. C первым пунктом все ясно - он просто явно задает результат вычисления 0! (а именно - 1). Подобное явное задание значений (или действий) на определенных входных параметрах (в данном случае - числе 0) называют условием выхода из рекурсии. Теперь попытаемся понять, что означает вторая запись. Правая часть равенства говорит о том, что функция ! (т.е. факториал) вычисляется для произвольного аргумента N. Правая часть содержит произведение. Первый множитель - само число N, второй - значение, которое функция принимает для N-1. Убедимся, что произведение этих величин действительно дает желаемый результат. Например, 4!=24=4·3! . Теперь разберемся, как вычислять по таким формулам.

Чтобы не затягивать процедуру, попытаемся найти факториал трех. Понятно, что первое выражение ничего нам не даст - оно может помочь вычислить только 0!. Поэтому воспользуемся вторым. Теперь самый важный момент - для вычисления 3! по второй формуле необходимо вычислить 2!. Для вычисления 2! (как и для вычисления 1! на следующем шаге) воспользуемся той же формулой. Получим следующую последовательность вызовов:

1. 3!=3·2!

2. 2!=2·1!

3. 1!=1·0!

0! задано явно, и у нас нет необходимости выполнять рекурсивный вызов для его вычисления (теперь понятно, почему первое выражение называют условием выхода из рекурсии). Зная 0!, последовательно находим 1!,2! и 3!. Обратите внимание на то, что если бы мы не задали условие выхода, алгоритм бы зациклился.

Теперь разберемся, как рекурсия программируется. Сразу хочется обратить внимание, что рекурсия неразрывно связана с понятием подпрограммы (процедуры или функции). На всех современных алгоритмических языках с рекурсивным оформлением подпрограмм не возникает никаких проблем, но обладатели некоторых устаревших версий Бейсика не смогут воспользоваться материалом этой статьи. Единственный совет в таком случае - перейти на что-нибудь посовременней (в Quick и Turbo Basic с рекурсией проблем не возникает).

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

1. a⁰=1 (условие выхода).

2. если a - четное, то a^x=(a²)^(x/2)

3. если a - нечетное, то a^x=a·(a²)^((x-1)/2)

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

function power(a:longint;x:word):longint;
 begin
 if x=0 then power:=1
 else if x mod 2 = 0 then power:=power(sqr(a),x div 2)
 else power:=a*power(sqr(a),x div 2);
 end; 

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

Речь идет о головоломке "Ханойские башни". Правила ее таковы. Имеется три стержня, на первом из них надето n дисков разного размера, причем нижнее кольцо - самое большое, следующее - чуть меньше и т.д. до самого маленького наверху. Требуется переложить все диски с первого стержня (источника) на третий (приемник), используя второй как промежуточный и придерживаясь следующих правил: за один раз можно брать только один диск и больший диск нельзя класть на меньший.

Можете самостоятельно подумать, как решить задачу при помощи циклических вычислений (алгоритм, мягко говоря, не очевиден, сложен и на практике никогда не используется). При помощи рекурсии задача решается элементарно:

1) если башня состоит из 0 дисков, ничего не делать;

2) иначе, если башня состоит из n>0 дисков, проделать следующие действия:

a) переложить башню из n-1 дисков на промежуточный стержень в качестве приемника;

b) переложить диск с источника на приемник;

c) переложить башню из n-1 дисков с промежуточного стержня на приемник.

Процедура, распечатывающая последовательность перемещений, и в данном случае дословно повторяет словесный алгоритм:

procedure Hanoi (Source, Destination, Temp : char; Count : byte);
 begin
 if Count>0 then
 begin
 Hanoi (Source, Temp, Destination, Count-1);
 Write (Source,'->', Destination,' ');
 Hanoi (Temp, Destination, Source, Count-1);
 end;
 end;

Вызовите процедуру, например, так: Hanoi ('1', '3', '2', 3) и просмотрите последовательность перемещений для трех дисков.

В заключение сделаю несколько общих (но очень важных) замечаний. Любой итерационный процесс можно заменить рекурсивным (подумайте, как), но не всегда стоит это проделывать (вспомните случай с факториалом). Многие рекурсивные подпрограммы можно заменить циклическими вычислениями, но при такой замене они, как правило, разрастаются и становятся малопонятными. В общем случае, рекурсия может быть успешно применена (и применяется) для обработки объектов, части которых имеют тот же тип, что и сам объект (любая часть дерева - дерево, любая часть массива - массив и т.п.). Следует обращать особое внимание на условие выхода, если оно задано некорректно, подпрограмма зациклится. Другая важная вещь - глубина рекурсии, то есть количество вызовов подпрограммой самой себя до срабатывания условия выхода. При каждом вызове подпрограммы занимается часть системного стека, так что если вы проделываете слишком много вложенных вызовов, он переполняется. Не передавайте рекурсивным процедурам громоздкие объекты (массивы и т.п.). Для обработки таких структур либо объявляйте их глобально, а передавайте индексы, либо размещайте их в памяти динамически, а передавайте указатель (в Бейсике могут возникнуть проблемы с этим способом). Устанавливайте большой размер стека, но если это не помогает - скорее всего ваш алгоритм далек от удачного; переделайте его. Для того, чтобы быстрее овладеть методом, старайтесь найти рекурсивное решение всех задач, предполагающих циклические вычисления, а затем разбирайтесь, какое решение эффективней (в большинстве таких случаев цикл все же лучше).

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

Денис МАРГОЛИН,
margolindenis@usa.net