Как преобразовать рекурсию, чтобы она работала быстрее?

Основные способы оптимизации рекурсии в C++ — это мемоизация (кэширование результатов) и переход на итеративный алгоритм.

1. Мемоизация (сверху вниз): Сохраняем результаты вычислений для уже обработанных входных данных, чтобы избежать повторных вызовов.

#include <unordered_map>
#include <iostream>

std::unordered_map<int, long long> fib_cache;

long long fib_memo(int n) {
    if (n <= 1) return n;
    // Проверяем кэш
    auto it = fib_cache.find(n);
    if (it != fib_cache.end()) {
        return it->second;
    }
    // Вычисляем и сохраняем
    long long result = fib_memo(n - 1) + fib_memo(n - 2);
    fib_cache[n] = result;
    return result;
}

int main() {
    std::cout << fib_memo(50) << std::endl; // Считает быстро
    return 0;
}

2. Итеративный подход (снизу вверх): Полностью заменяем рекурсивные вызовы циклом. Это устраняет накладные расходы на вызов функции и работу со стеком.

long long fib_iterative(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

3. Ручное управление стеком: Для сложных рекурсивных алгоритмов (например, обход дерева) можно эмулировать стек вызовов.

#include <stack>

struct Frame {
    TreeNode* node;
    int state; // 0: посетить левое поддерево, 1: обработать узел, 2: посетить правое
};

void inorder_iterative(TreeNode* root) {
    std::stack<Frame> st;
    st.push({root, 0});
    while (!st.empty()) {
        auto& f = st.top();
        if (!f.node || f.state == 2) {
            st.pop();
            continue;
        }
        if (f.state == 0) {
            f.state = 1;
            st.push({f.node->left, 0});
        } else if (f.state == 1) {
            std::cout << f.node->val << " ";
            f.state = 2;
            st.push({f.node->right, 0});
        }
    }
}

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