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

Теория

Зачем нужен этот пункт

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

На самом деле рекурсия удобна там, где задача естественно разбивается на такую же задачу меньшего размера. Например:

В этом пункте рассматриваются:

Что такое рекурсивная функция

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

Простейшая форма прямой рекурсии выглядит так:

void function(void)
{
    function();
}

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

Правильная рекурсивная функция должна иметь:

Прямая рекурсия

Прямая рекурсия возникает, когда функция явно вызывает саму себя в своём теле.

void countdown(int n)
{
    if (n <= 0)
    {
        return;
    }

    printf("%d\n", n);

    countdown(n - 1);
}

Здесь функция countdown вызывает саму себя:

countdown(n - 1);

Но при каждом вызове значение n уменьшается. Когда n становится меньше или равно нулю, выполняется return, и рекурсия останавливается.

Косвенная рекурсия

Косвенная рекурсия возникает, когда функция вызывает не саму себя напрямую, а другую функцию, которая затем снова приводит к вызову первой функции.

void functionA(int n);
void functionB(int n);

void functionA(int n)
{
    if (n <= 0)
    {
        return;
    }

    printf("A: %d\n", n);
    functionB(n - 1);
}

void functionB(int n)
{
    if (n <= 0)
    {
        return;
    }

    printf("B: %d\n", n);
    functionA(n - 1);
}

Здесь functionA вызывает functionB, а functionB вызывает functionA. Поэтому рекурсия есть, хотя внутри functionA нет строки functionA(...).

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

Две обязательные части рекурсии

Почти любую учебную рекурсивную функцию можно представить как конструкцию из двух частей:

тип function(параметры)
{
    if (условие_выхода)
    {
        return простой_результат;
    }

    return выражение_с_рекурсивным_вызовом;
}

Условие выхода нужно, чтобы рекурсия когда-то закончилась. Рекурсивный шаг нужен, чтобы перейти к более простой версии задачи.

Например, для факториала:

Факториал

Факториал неотрицательного целого числа определяется так:

0! = 1
n! = n * (n - 1)! при n > 0

Это определение уже рекурсивно: факториал числа n выражается через факториал меньшего числа.

#include <stdio.h>

long factorial(int n);

int main(void)
{
    int n;

    printf("Введите n: ");
    scanf("%d", &n);

    printf("factorial = %ld\n", factorial(n));

    return 0;
}

long factorial(int n)
{
    if (n < 0)
    {
        return 0;
    }

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

    return n * factorial(n - 1);
}

Здесь:

Как выполняется factorial(4)

Рассмотрим вызов:

factorial(4)

Он раскрывается так:

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1 * factorial(0)
= 4 * 3 * 2 * 1 * 1
= 24

Рекурсия сначала углубляется до базового случая factorial(0), а затем результаты начинают возвращаться обратно.

Стек вызовов

При каждом вызове функции создаётся новый набор её локальных переменных и параметров. Это относится и к рекурсивным вызовам.

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

    return n * factorial(n - 1);
}

При вызове factorial(4) одновременно существуют несколько активных вызовов:

factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)

У каждого вызова свой параметр n. Значение n в одном вызове не является той же самой переменной, что n в другом вызове.

Механизм, который хранит активные вызовы функций, обычно называют стеком вызовов.

Автоматические локальные переменные при рекурсии

Локальные переменные, объявленные внутри функции, создаются заново при каждом её вызове.

#include <stdio.h>

void show(int n)
{
    int local = n * 10;

    printf("n = %d, local = %d\n", n, local);

    if (n > 0)
    {
        show(n - 1);
    }
}

При каждом новом вызове show создаётся своя переменная local. Значения локальных переменных разных вызовов не смешиваются.

Это позволяет рекурсии работать корректно, но требует памяти: чем глубже рекурсия, тем больше активных вызовов хранится в стеке.

Бесконечная рекурсия

Если условие выхода отсутствует или никогда не выполняется, возникает бесконечная рекурсия.

void bad(int n)
{
    printf("%d\n", n);

    bad(n + 1);
}

Здесь значение n увеличивается, но условия остановки нет. Функция будет вызывать себя снова и снова.

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

void bad(int n)
{
    if (n == 0)
    {
        return;
    }

    bad(n);
}

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

Рекурсивный вывод чисел

Рекурсия может выполнять действия до рекурсивного вызова или после него.

#include <stdio.h>

void printDown(int n)
{
    if (n <= 0)
    {
        return;
    }

    printf("%d ", n);
    printDown(n - 1);
}

void printUp(int n)
{
    if (n <= 0)
    {
        return;
    }

    printUp(n - 1);
    printf("%d ", n);
}

Вызов printDown(5) выведет:

5 4 3 2 1

А вызов printUp(5) выведет:

1 2 3 4 5

Разница в том, где расположен printf: до рекурсивного вызова или после него.

Рекурсивное возведение в степень

Степень можно определить рекурсивно:

x^0 = 1
x^n = x * x^(n - 1), если n > 0
#include <stdio.h>

double power(double x, int n);

int main(void)
{
    printf("%f\n", power(2.0, 10));
    return 0;
}

double power(double x, int n)
{
    if (n < 0)
    {
        return 1.0 / power(x, -n);
    }

    if (n == 0)
    {
        return 1.0;
    }

    return x * power(x, n - 1);
}

Здесь n == 0 — условие выхода. При положительном n функция уменьшает степень на единицу. При отрицательном n используется свойство:

x^(-n) = 1 / x^n

Более быстрый вариант степени

Предыдущая функция делает n рекурсивных шагов. Можно использовать более быстрый способ — возведение в степень через деление показателя пополам.

double fastPower(double x, int n)
{
    double half;

    if (n < 0)
    {
        return 1.0 / fastPower(x, -n);
    }

    if (n == 0)
    {
        return 1.0;
    }

    if (n % 2 == 0)
    {
        half = fastPower(x, n / 2);
        return half * half;
    }

    return x * fastPower(x, n - 1);
}

Если показатель чётный, задача x^n сводится к x^(n/2). Это уменьшает количество рекурсивных вызовов.

Числа Фибоначчи

Последовательность Фибоначчи определяется так:

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2), если n > 1

Это определение легко записать рекурсивно.

#include <stdio.h>

long fibonacci(int n);

int main(void)
{
    int n;

    printf("Введите n: ");
    scanf("%d", &n);

    printf("F(%d) = %ld\n", n, fibonacci(n));

    return 0;
}

long fibonacci(int n)
{
    if (n < 0)
    {
        return 0;
    }

    if (n == 0)
    {
        return 0;
    }

    if (n == 1)
    {
        return 1;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Такой код хорошо показывает идею рекурсии, но для больших n он работает медленно.

Почему простой fibonacci медленный

В функции:

return fibonacci(n - 1) + fibonacci(n - 2);

каждый вызов порождает ещё два вызова. Многие значения вычисляются повторно.

Например, при вычислении fibonacci(5) значение fibonacci(3) будет вычисляться несколько раз.

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   └── fibonacci(2)
└── fibonacci(3)

Поэтому рекурсивное определение не всегда означает эффективную программу. Для чисел Фибоначчи в простом учебном варианте часто лучше использовать цикл.

Итеративный вариант Фибоначчи

long fibonacciIterative(int n)
{
    int i;
    long a = 0;
    long b = 1;
    long next;

    if (n < 0)
    {
        return 0;
    }

    if (n == 0)
    {
        return 0;
    }

    for (i = 2; i <= n; i++)
    {
        next = a + b;
        a = b;
        b = next;
    }

    return b;
}

Этот вариант не создаёт дерево рекурсивных вызовов и работает значительно быстрее для больших n.

Вывод: рекурсия удобна для выражения идеи, но не всегда даёт самый эффективный алгоритм.

Рекурсивная сумма элементов массива

Массив тоже можно обработать рекурсивно: сумма первых n элементов равна сумме первых n - 1 элементов плюс последний элемент.

#include <stdio.h>

int arraySum(const int a[], int n);

int main(void)
{
    int values[] = { 2, 4, 6, 8, 10 };

    printf("sum = %d\n", arraySum(values, 5));

    return 0;
}

int arraySum(const int a[], int n)
{
    if (n <= 0)
    {
        return 0;
    }

    return arraySum(a, n - 1) + a[n - 1];
}

Условие выхода: n <= 0. Рекурсивный шаг: уменьшить количество рассматриваемых элементов на один.

Рекурсивный поиск в массиве

Можно рекурсивно искать значение в массиве.

#include <stdio.h>

int contains(const int a[], int n, int target);

int main(void)
{
    int values[] = { 5, 8, 12, 20 };

    if (contains(values, 4, 12))
    {
        printf("Найдено\n");
    }
    else
    {
        printf("Не найдено\n");
    }

    return 0;
}

int contains(const int a[], int n, int target)
{
    if (n <= 0)
    {
        return 0;
    }

    if (a[n - 1] == target)
    {
        return 1;
    }

    return contains(a, n - 1, target);
}

Функция проверяет последний элемент текущей части массива. Если элемент не найден, задача уменьшается до массива длины n - 1.

Рекурсивный бинарный поиск

Бинарный поиск хорошо подходит для рекурсивной записи. Он работает только с отсортированным массивом.

#include <stdio.h>

int binarySearch(const int a[], int left, int right, int target);

int main(void)
{
    int a[] = { 2, 5, 8, 12, 16, 23, 38 };
    int index;

    index = binarySearch(a, 0, 6, 16);

    if (index != -1)
    {
        printf("Индекс = %d\n", index);
    }
    else
    {
        printf("Не найдено\n");
    }

    return 0;
}

int binarySearch(const int a[], int left, int right, int target)
{
    int middle;

    if (left > right)
    {
        return -1;
    }

    middle = left + (right - left) / 2;

    if (a[middle] == target)
    {
        return middle;
    }

    if (target < a[middle])
    {
        return binarySearch(a, left, middle - 1, target);
    }

    return binarySearch(a, middle + 1, right, target);
}

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

Рекурсивная обработка строки

Строка в C заканчивается символом '\0'. Этот символ можно использовать как условие выхода.

#include <stdio.h>

int stringLength(const char *s);

int main(void)
{
    printf("length = %d\n", stringLength("hello"));
    return 0;
}

int stringLength(const char *s)
{
    if (s == NULL)
    {
        return 0;
    }

    if (*s == '\0')
    {
        return 0;
    }

    return 1 + stringLength(s + 1);
}

Если текущий символ — '\0', длина оставшейся строки равна нулю. Иначе длина равна 1 плюс длина строки, начинающейся со следующего символа.

Рекурсивный вывод строки наоборот

#include <stdio.h>

void printReverse(const char *s);

int main(void)
{
    printReverse("hello");
    printf("\n");

    return 0;
}

void printReverse(const char *s)
{
    if (s == NULL || *s == '\0')
    {
        return;
    }

    printReverse(s + 1);
    putchar(*s);
}

Функция сначала вызывает себя для следующего символа, а потом выводит текущий символ. Поэтому символы выводятся в обратном порядке.

Рекурсивный алгоритм Евклида

Наибольший общий делитель двух чисел можно найти рекурсивно.

#include <stdio.h>

int gcd(int a, int b);

int main(void)
{
    printf("%d\n", gcd(48, 18));
    return 0;
}

int gcd(int a, int b)
{
    if (b == 0)
    {
        return a;
    }

    return gcd(b, a % b);
}

Условие выхода: второй аргумент стал равен нулю. Рекурсивный шаг: заменить пару (a, b) на (b, a % b).

Хвостовая рекурсия

Хвостовая рекурсия — это случай, когда рекурсивный вызов является последним действием функции.

void printDown(int n)
{
    if (n <= 0)
    {
        return;
    }

    printf("%d ", n);
    printDown(n - 1);
}

После вызова printDown(n - 1) функция больше ничего не делает. Это хвостовая рекурсия.

А в факториале:

return n * factorial(n - 1);

после возвращения из factorial(n - 1) ещё нужно выполнить умножение на n. Поэтому это не хвостовая рекурсия.

Рекурсия и циклы

Многие рекурсивные функции можно переписать через цикл.

Рекурсивный факториал:

long factorialRecursive(int n)
{
    if (n <= 1)
    {
        return 1;
    }

    return n * factorialRecursive(n - 1);
}

Итеративный факториал:

long factorialIterative(int n)
{
    long result = 1;
    int i;

    for (i = 2; i <= n; i++)
    {
        result *= i;
    }

    return result;
}

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

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

Когда рекурсия подходит хорошо

Рекурсия особенно удобна, когда задача или данные имеют вложенную структуру.

Если задача просто повторяет одно действие много раз по счётчику, цикл часто будет проще и эффективнее.

Глубина рекурсии

Глубина рекурсии — это количество активных рекурсивных вызовов, которые одновременно находятся в стеке.

factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)

Здесь глубина рекурсии примерно равна 5.

Если глубина слишком большая, стек вызовов может переполниться. Это называется переполнением стека.

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

Рекурсия с указателем на функцию

Рекурсивная функция может использовать и указатель на функцию. Например, можно рекурсивно искать корень функции на отрезке методом деления пополам.

#include <stdio.h>
#include <math.h>

double root(double (*f)(double), double left, double right, double eps);
double testFunction(double x);

int main(void)
{
    double result;

    result = root(testFunction, 0.0, 2.0, 0.0001);

    printf("root = %f\n", result);

    return 0;
}

double root(double (*f)(double), double left, double right, double eps)
{
    double middle;

    middle = (left + right) / 2.0;

    if (fabs(right - left) < eps)
    {
        return middle;
    }

    if (f(left) * f(middle) <= 0.0)
    {
        return root(f, left, middle, eps);
    }

    return root(f, middle, right, eps);
}

double testFunction(double x)
{
    return x * x - 2.0;
}

Здесь функция root не знает заранее, какую математическую функцию нужно исследовать. Она получает её через параметр double (*f)(double).

Рекурсия и глобальные переменные

Иногда для наблюдения за рекурсией используют глобальный счётчик вызовов.

#include <stdio.h>

int callCount = 0;

long factorial(int n)
{
    callCount++;

    if (n <= 1)
    {
        return 1;
    }

    return n * factorial(n - 1);
}

int main(void)
{
    printf("%ld\n", factorial(5));
    printf("Количество вызовов: %d\n", callCount);

    return 0;
}

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

Пошаговая проверка рекурсивной функции

Чтобы проверить рекурсивную функцию, удобно задать себе три вопроса:

  1. Есть ли условие выхода?
  2. Приближает ли каждый рекурсивный вызов к условию выхода?
  3. Правильно ли функция решает простейший случай?

Для факториала:

Если хотя бы один из этих пунктов нарушен, рекурсивная функция скорее всего будет работать неправильно.

Типичные ошибки

Ошибка 1. Нет условия выхода

void f(void)
{
    f();
}

Функция вызывает себя бесконечно. Нужно добавить условие остановки.

Ошибка 2. Рекурсивный вызов не приближает к выходу

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

    return n * factorial(n);
}

Значение n не уменьшается, поэтому функция не дойдёт до n == 0.

Ошибка 3. Неправильный базовый случай

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

    return n * factorial(n - 1);
}

Для n == 0 такая функция не остановится правильно. Лучше явно обработать n == 0 или n <= 1.

Ошибка 4. Слишком большая глубина рекурсии

countdown(1000000);

Даже если функция логически правильная, слишком глубокая рекурсия может привести к переполнению стека.

Ошибка 5. Неэффективная рекурсия

long fibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Эта функция многократно пересчитывает одни и те же значения. Для больших n лучше использовать цикл или запоминание уже вычисленных результатов.

Ошибка 6. Путаница между действиями до и после рекурсивного вызова

printReverse(s + 1);
putchar(*s);

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

Ошибка 7. Рекурсия там, где проще цикл

int sumToN(int n)
{
    if (n == 0)
    {
        return 0;
    }

    return n + sumToN(n - 1);
}

Такая функция работает, но для простой суммы от 1 до n цикл часто понятнее и безопаснее.

Практические рекомендации

Мини-разбор программы

Программа показывает три рекурсивные функции: факториал, сумму массива и вывод строки наоборот.

#include <stdio.h>

long factorial(int n);
int arraySum(const int a[], int n);
void printReverse(const char *s);

int main(void)
{
    int values[] = { 1, 2, 3, 4, 5 };

    printf("factorial(5) = %ld\n", factorial(5));
    printf("sum = %d\n", arraySum(values, 5));

    printf("reverse: ");
    printReverse("hello");
    printf("\n");

    return 0;
}

long factorial(int n)
{
    if (n < 0)
    {
        return 0;
    }

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

    return n * factorial(n - 1);
}

int arraySum(const int a[], int n)
{
    if (n <= 0)
    {
        return 0;
    }

    return arraySum(a, n - 1) + a[n - 1];
}

void printReverse(const char *s)
{
    if (s == NULL || *s == '\0')
    {
        return;
    }

    printReverse(s + 1);
    putchar(*s);
}

Разберём программу:

Что нужно запомнить

Самопроверка перед переходом дальше

  1. Что такое рекурсивная функция?
  2. Чем прямая рекурсия отличается от косвенной?
  3. Что такое условие выхода из рекурсии?
  4. Что такое рекурсивный шаг?
  5. Почему функция без условия выхода опасна?
  6. Что происходит с локальными переменными при каждом рекурсивном вызове?
  7. Что такое стек вызовов?
  8. Как рекурсивно вычисляется факториал?
  9. Почему factorial(0) должен возвращать 1?
  10. Почему простой рекурсивный Фибоначчи работает медленно?
  11. Когда рекурсию лучше заменить циклом?
  12. Как рекурсивно посчитать сумму элементов массива?
  13. Как строковый символ '\0' помогает остановить рекурсию?
  14. Почему действие после рекурсивного вызова выполняется при возврате из глубины рекурсии?
  15. Что такое переполнение стека?
  16. В каких задачах рекурсия особенно удобна?