Особенности программирования рекурсивных функций

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

.void main() void F() void F() void F()
{ { { {
F(); ..if()F(); ...if()F(); ...if()F();
} } } }

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

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

-формальные параметры рекурсивной функции представляют начальное состояние для текущего шага процесса;

- фактические параметры рекурсивного вызова представляют начальное состояние для следующего шага, в который производится переход из текущего при рекурсивном вызове;

-автоматические переменные представляют внутренние характеристики процесса на текущем шаге его выполнения;

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

Из сказанного следует, что формальные параметры рекурсивной функции, внешние и локальные переменные не могут быть взаимозаменяемы, как это иногда делается в обычных функциях. Кроме того, каждый новый рекурсивный вызов порождает новый "экземпляр" формальных параметров и локальных переменных, причем старый "экземпляр" не уничтожается, а сохраняется в стеке по принципу вложенности. Здесь имеет место единственный случай, когда одному имени переменной в процессе работы программы соответствуют несколько ее "экземпляров". Рассмотрим подробнее этот парадокс. Как уже было сказано, рекурсивный вызов функции внешне выглядит как создание в программе ее копии. В действительности же алгоритмическая компонента функции не копируется, а создается копия только с ее локальных данных. Происходит это в такой последовательности :

- в стеке резервируется место для формальных параметров, в которые записываются значения фактических параметров. Обычно это производится в порядке, обратном их следованию в списке ;

- при вызове функции в стек записывается точка возврата - адрес той части программы, где находится вызов функции ;

- в начале тела функции в стеке резервируется место для локальных (автоматических) переменных.

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

Все сказанное воспринимается естественно, если не забывать о представлении рекурсивной программы как процесса. Тогда естественно, что все шаги процесса являются идентичными, а отличаются только начальным состоянием, текущими параметрами и точкой возврата. Это есть не что иное как фрейм стека рекурсивной функции. Если программа помнит " историю" процесса, то естественным выглядит и хранение в стеке этих фреймов.

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

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

Содержание раздела