Рекурсивные функции. При обработке динамических структур полезно использовать рекурсивные функции

При обработке динамических структур полезно использовать рекурсивные функции. Рекурсивные функции – это функции, вызывающие сами себя. Классический пример рекурсивного вызова функции – вычисление факториала. Для любого целого числа N ³ 0 значение факториала N (обозначается N!) определяется по следующему алгоритму:

0! = 1,

если N > 0, то N! = N * (N – 1)!,
то есть факториал определен рекурсивно (в терминах самого себя).

Для того чтобы рекурсия завершилась, необходимо задавать условие окончания рекурсии, в данном случае 0! =1.

Рекурсивные алгоритмы можно программировать с помощью обычных нерекурсивных приемов, например, используя рекуррентные формулы в цикле, можно описать функцию вычисления факториала:

int factorial (int N)

{ int rez =1; /* начальное значение факториала */

int i;

if (N > 0)

for (i=1; i <= N; i++) rez *= i;

return rez;

}

Однако можно реализовать вычисление факториала, исходя из его рекурсивного определения:

int factorial (int N)

{ if (N <= 0) return 1;

else return (N * factorial (N – 1));

}

void main ()

{ printf (“4! = %d “, factorial (4));

}

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

factorial (4)

factorial (3)

factorial (2)

factorial (1)

factorial (0)

Последний вызов функции возвращает значение 1 для вызова factorial (1) и далее в следующем порядке:

порядок возвратов: возвращаемое значение:

return (1) 1

return (1 * 0!) 1

return (2 * 1!) 2

return (3 * 2!) 6

return (4 * 3!) 24

Последнее значение 24 будет возвращено функции main.

Каждый вызов функции factorial () в действительности создает новый объект для хранения значения аргумента N, поскольку при очередном вызове оно помещается в стек командой push. Текущим значением N для функции factorial () является то, которое передано ей при самом последнем вызове.

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