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

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

При каждом обращении к рекурсивной функции создается новый набор объектов автоматической памяти, локализованных в теле функции.

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

Еще раз отметим, что различают прямую и косвенную рекурсии. Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна. Если в теле функции явно используется вызов этой же функции, то имеет место прямая рекурсия, т.е. функция, по определению, рекурсивная (иначе -самовызываемая или самовызывающая: self-calling). Классический пример - функция для вычисления факториала неотрицательного целого числа.

Для отрицательного аргумента результат (по определению факториала) не существует. В этом случае функция возвратит нулевое значение. Для нулевого параметра функция возвращает значение 1, так как, по определению, 0! равен 1. В противном случае вызывается та же функция с уменьшенным на 1 значением параметра и результат умножается на текущее значение параметра. Тем самым для положительного значения параметра k организуется вычисление произведения

Обратите внимание, что последовательность рекурсивных обращений к функции fact() прерывается при вызове fact(0). Именно этот вызов приводит к последнему значению 1 в произведении, так как последнее выражение, из которого вызывается функция, имеет вид: l*fact(l-l)

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

При обращении вида ехро(2.0, 3) рекурсивно выполняются вызовы функции ехро( ) с изменяющимся вторым аргументом: ехро(2.0,3), ехро(2.0,2), ехро(2.0,1), ехро(2.0,0). При этих вызовах последовательно вычисляется произведение

и формируется нужный результат.

Вызов функции для отрицательного значения степени, например,

эквивалентен вычислению выражения

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

В качестве еще одного примера рекурсии рассмотрим функцию определения с заданной точностью eps корня уравнения f(x) = 0 на отрезке [а, b]. Предположим для простоты, что исходные данные задаются без ошибок, т.е. eps > 0, f(a) * f(b) < 0, b > а, и вопрос о возможности существования нескольких корней на отрезке [а, b] нас не интересует. Не очень эффективная рекурсивная функция для решения поставленной задачи содержится в следующей программе:

Результат выполнения программы:

В рассматриваемой программе пришлось использовать библиотечную функцию exit( ), прототип которой размещен в заголовочном файле stdlib.h Функция exit( ) позволяет завершить выполнение программы и возвращает операционной системе значение своего параметра.

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

В литературе по программированию рекурсиям уделено достаточно внимания как в теоретическом плане, так и в плане рассмотрения механизмов реализации рекурсивных алгоритмов. Сравнивая рекурсию с итерационными методами, отмечают, что рекурсивные алгоритмы наиболее пригодны в случаях, когда поставленная задача или используемые данные определены рекурсивно (см., например, Вирт Н. Алгоритмы + структуры данных = программы - М.: Мир, 1985. - 406 с.). В тех случаях, когда вычисляемые значения определяются с помощью простых рекуррентных соотношений, гораздо эффективнее применять итеративные методы. Таким образом, определение корня математической функции, возведение в степень и вычисление факториала только иллюстрируют схемы организации рекурсивных функций, но не являются примерами эффективного применения рекурсивного подхода к вычислениям.

В следующей главе, посвященной структурам и объединениям, мы рассмотрим (§6.4) динамические информационные структуры, которые включают рекурсивность в само определение обрабатываемых данных. Именно для таких данных применение рекурсивных алгоритмов не имеет конкуренции со стороны итерационных методов.