2. Применение рекурсий
 

Схема рекурсивной функции и особенности ее выполнения были подробно рассмотрены нами ранее.

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

Применение рекурсий во многих случаях дает весьма простые и изящные решения задач. В то же время рекурсивный алгоритм может оказаться неэффективным. Примером может служить рекурсивная функция определения числа Фибоначчи. В ней имеются два рекурсивных вызова, причем второй рекурсивный вызов не использует вычисления, выполненные во время первого вызова. Это приводит к повторным вычислениям. Время вычисления F_N+1 примерно в 1,618 раза («золотое сечение») больше времени вычисления F_N.
Пример . Вычисление чисел Фибоначчи, которые определяются рекуррентными соотношениями: F₀ = О, F₁ = 1, F_n= F_n-1 + F_n-2. Рекурсивная функция на Си будет иметь вид:

int Fib(int n)
{if (n < 2) return n;
else return (Fib(n - 1) + Fib(n - 2)); }

Каждое обращение к функции Fib(n) при n > 1 приводит к двум дальнейшим обращениям, т.е. общее число обращений растет экспоненциально, сложность алгоритма 0(2ⁿ). В то же время нерекурсивный вариант функции, приведенный ниже, имеет временную сложность О(n).

int Fib(int n)
{int i, x, у, z;
if (n < 2) return n;
x = 0;                         /* Fo */
y=1;                        /* F1 */
for (i =2; i≤n; i++)
{z = x+y; x = y; y = z;
}
return z;
}