4. Рекурсия

Задание

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

  1. Функция sum_array для вычисления суммы элементов массива. Сумма элементов массива есть сумма его нулевого элемента и сумма остальных элементов.
  2. Функция вычисления n-ного числа Фибоначчи. \( F_0 = 1, F_1 = 1, F_n = F_{n - 1} + F_{n - 2} \) Нарисуйте дерево, иллюстрирующее рекурсивный процесс, который порождается этой функцией.
  3. Функция преобразования числа в строку.

Основные понятия

Рекурсивная функция — это функция, вызывающая сама себя.

Классическим примером является функция вычисления факториала:

\[n! = n \cdot (n - 1) \cdot (n - 2) \cdot \cdot \cdot 3 \cdot 2 \cdot 1\]

Рекуррентная формула:

\[\begin{split}n! = \begin{cases} 1 & n = 0 \\ n \cdot (n - 1) & n < 0 \end{cases}\end{split}\]

Запишем функцию на языке С:

int factorial(int n)
{
    if (n == 0) {
        return 1;
    }

    return n * factorial(n - 1);
}

Проиллюстрируем процесс, порождаемый этой функцией для \(n = 6\):

factorial(6)
6 * factorial(5)
6 * 5 * factorial(4)
6 * 5 * 4 * factorial(3)
6 * 5 * 4 * 3 * factorial(2)
6 * 5 * 4 * 3 * 2 * factorial(1)
6 * 5 * 4 * 3 * 2 * 1 * factorial(0)
6 * 5 * 4 * 3 * 2 * 1 * 1
6 * 5 * 4 * 3 * 2 * 1
6 * 5 * 4 * 3 * 2
6 * 5 * 4 * 6
6 * 5 * 24
6 * 5 * 24
6 * 120
720

Можно реализовать эту функцию иначе:

int factorial_iter(int product, int counter, int max_count)
{
    if (counter > max_count) {
        return product;
    }

    return factorial_iter(product * counter, counter + 1, max_count);
}

int factorial(int n)
{
    return factorial_iter(1, 1, n);
}

Проиллюстрируем процесс, порождаемый этими функциями для \(n = 6\):

factorial(6)
factorial_iter(1, 1, 6)
factorial_iter(1, 2, 6)
factorial_iter(2, 3, 6)
factorial_iter(6, 4, 6)
factorial_iter(24, 5, 6)
factorial_iter(120, 6, 6)
factorial_iter(720, 7, 6)
720

Оба процесса получают одну и ту же последовательность частичных произведений, но их «формы» существенно отличаются.

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

Второй процесс не растет и не сжимается. Такой процесс называется итеративным.

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

Важно не смешивать понятие рекурсивной функции и рекурсивного процесса. Говоря о рекурсивной функции, имеют в виду факт синтаксиса: определение этой функции прямо или косвенно ссылается на эту функцию. Говоря о процессе, подразумевают развитие процесса. Так, во втором случае рекурсивная функция factorial описывает итеративный процесс.

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

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