Рекурсивные функции

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

Функция называется косвенно рекурсивной, если она содержит обращение к другой функции, которая содержит прямой или косвенный вызов определяемой (первой) функции.

Если в теле функции явно используется вызов этой функции, то имеет место прямая рекурсия.

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

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

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

При выполнении рекурсивной функции происходит многократный ее вызов, при этом

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

2) переменным с классом памяти extern и static память выделяется один раз, которая сохраняется в течение всего времени программы;

3) вызов рекурсивной функции происходит до тех пор, пока не будет получено конкретное значение без рекурсивного вызова функции.

Примеры:

1) Определить функцию, возвращающую значение факториала целого числа. Факториал определятся только для положительных чисел формулой: , и факториал нуля равен 1 (0! =1).

Определение факториала можно переписать в виде “математической рекурсии“: , то есть факториал вычисляется через факториал. Соответственно определение функции:

Поиск по сайту: