Стек. Реализация рекурсии: что происходит при вызове функции

Модуль "Стек" • урок 6 из 8 • ~8 минут

Что такое рекурсия

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

Смысл приема - свести сложную задачу к такой же, но поменьше: факториал n через факториал n - 1, обход дерева через обход поддеревьев. А чтобы цепочка не оказалась бесконечной, в теле функции обязано быть условие завершения - базис рекурсии, который рано или поздно срабатывает (например, счетчик дошел до нуля).

Стек. Реализация рекурсии: кадр вызова

Когда f(x) вызывает f(x - 1), выполнение внешней функции приостанавливается. Процессору нужно запомнить, где она остановилась и какими были ее переменные. Для этого используется знакомый вам по уроку "Стек в железе" аппаратный стек: при каждом вызове туда проталкивается кадр стека (stack frame), содержащий:

• адрес возврата - с какой инструкции продолжить после вызова;
• формальные параметры текущего вызова;
• локальные переменные функции.

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

Трассировка: факториал

Классический пример. Параметр i передается по значению - у каждого вызова своя независимая копия:

int f(int i) {
    if (i > 0) {
        return i * f(i - 1);
    } else {
        return 1; /* базис рекурсии */
    }
}

Проследим вызов f(3):

1. f(3) приостанавливается, ждет результат f(2). В стеке кадр с i = 3.
2. f(2) ждет f(1). В стеке кадры с i = 3 и i = 2.
3. f(1) ждет f(0). В стеке уже три кадра.
4. f(0) достигает базиса и возвращает 1.
5. Стек сворачивается (unwinding): f(1) считает 1 * 1, f(2) - 2 * 1, f(3) - 3 * 2. Ответ: 6.

Глубина стека росла до четырех кадров - и все они существовали одновременно. Теперь понятно, почему слишком глубокая рекурсия кончается переполнением стека: кадры съедают его целиком, и программа падает.

Сведение рекурсии к итерации

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

/* Stack и функции Create, Push, Pop, Top, Empty -
   из предыдущих уроков темы */

int f(int n) {
    int res = 1;
    Stack s;
    Create(&s);

    while (n > 0) {
        Push(&s, n); /* сохраняем состояния в явный стек */
        n--;
    }

    while (!Empty(&s)) {
        res *= Top(&s); /* достаем состояния и вычисляем */
        Pop(&s);
    }

    return res;
}

Для факториала перевод тривиален. У более хитрых рекурсий - скажем, функции Аккермана или обхода дерева - управление явным стеком требует заметно более сложного кода, но принцип тот же: то, что процессор делал неявно, мы теперь делаем явно.