3. Рекуррентные соотношения

Рекурсивным называется способ построения объекта (понятия, системы, описание действия), в котором определение объекта включает аналогичный объект (понятие, систему, действие) в виде некоторой его части. Общеизвестный пример рекурсивного изображения - предмет между двумя зеркалами - в каждом из них виден бесконечный ряд отражений. Более серьезные примеры рекурсии можно обнаружить математике :

- рекуррентные соотношения определяют некоторый элемент последовательности через несколько предыдущих. Например, числа Фиббоначи : F(n)=F(n-1)+F(n-2), где F(0)=1, F(1)=1. Если рассматривать этот ряд от младших членов к старшим, способ его построения задается циклическим алгоритмом, а если наоборот, от заданного n=n0 , то способ определения этого элемента через предыдущие будет рекурсивным.

Особенности работы рекурсивной функции. Рекурсивные функции лишь на первый взгляд выглядят как обычные фрагменты программ. Чтобы ощутить их специфику, достаточно мысленно проследить по тексту программы процесс ее выполнения. В обычной программе мы будем следовать по цепочке вызовов функций, но ни разу повторно не войдем в один и тот же фрагмент, пока из него не вышли. Можно сказать, что процесс выполнения программы " ложится" однозначно на текст программы. Другое дело - рекурсия. Если попытаться отследить по тексту программы процесс ее выполнения, то мы придем к такой ситуации : войдя в рекурсивную функцию F, мы " движемся" по ее тексту до тех пор, пока не встретим ее вызова, после чего мы опять начнем выполнять ту же самую функцию сначала. При этом следует отметить самое важное свойство рекурсивной функции - ее первый вызов еще не закончился. Чисто внешне создается впечатление, что текст функции воспроизводится (копируется) всякий раз, когда функция сама себя вызывает :

void main() void F() void F() void F()

{ { { {

F(); ..if()F(; ...if()F(); ...if()F();

} } } }

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

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

Итак, перечислим последовательность и содержание шагов в проектировании и " сведении вместе" фрагментов рекурсивной функции.

1. . " Зацепить рекурсию" - определить, что составляет шаг рекурсивного алгоритма;

2. . Инварианты рекурсивного алгоритма. Основные свойства, соотношения, которые присутствуют на входе рекурсивной функции и которые сохраняются до следующего рекурсивного вызова, но уже в состоянии, более близком к цели;

3. . Глобальные переменные общие данные процесса в целом ;

4. . Начальное состояние шага рекурсивного алгоритма формальные параметры рекурсивной функции ;

5. . Ограничения рекурсии обнаружение " успеха" - достижения цели на текущем шаге рекурсии и отсечение " неудач" - заведомо неприемлемых вариантов;

6. . Правила перебора возможных вариантов способы формирования рекурсивного вызова;

7. . Начальное состояние следующего шага фактические параметры рекурсивного вызова ;

8. . Содержание и способ обработки результата полный перебор с сохранением всех допустимых вариантов, первый возможный, оптимальный;

9. . Условия первоначального вызова рекурсивной функции в main.