Информатика и технология программирования


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


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


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

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

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



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




Начало  Назад  Вперед