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

Ответ: Tail-call, итерация, memoization - методы оптимизации рекурсии

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

Способ 1: Хвостовая рекурсия (Tail-call optimization)

Tail-call - когда рекурсивный вызов это последняя операция функции:

// ❌ НЕ хвостовая рекурсия
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // Умножение ПОСЛЕ вызова
}

// ✅ Хвостовая рекурсия
int factorial_tail(int n, int acc = 1) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc);  // Вызов в конце
}

Компилятор может оптимизировать хвостовую рекурсию, превратив её в цикл:

// Как компилятор видит tail-call
int factorial_tail(int n, int acc = 1) {
loop:  // goto вместо рекурсии
    if (n <= 1) return acc;
    int temp = n * acc;
    n = n - 1;
    acc = temp;
    goto loop;  // Возврат, а не рекурсивный вызов
}

Компилирование с флагом для TCO:

g++ -O2 -foptimize-sibling-calls program.cpp
g++ -O3 program.cpp  # O3 обычно включает TCO

Способ 2: Конвертация в итерацию

Самый быстрый способ - совсем избегнуть рекурсии:

// ❌ Рекурсия: O(n) stack frames
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// ✅ Итерация: O(1) stack
int fibonacci_iter(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Сравнение для fib(40):

• Рекурсия: ~1000 мс (выполнение экспоненциального количества вызовов)
• Итерация: < 1 мкс

Способ 3: Memoization (кэширование результатов)

Идея: сохранить результаты уже вычисленных вызовов:

std::map<int, long long> memo;

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

Сложность:

• Без memoization: O(2^n)
• С memoization: O(n)

Для fib(40):

• Без memo: ~330 млн. вызовов
• С memo: 40 вызовов

Способ 4: Dynamic Programming (восходящий подход)

long long fibonacci_dp(int n) {
    if (n <= 1) return n;
    
    std::vector<long long> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

Преимущества:

• Избегаем рекурсии
• Нет вызовов функций
• Лучше для кэша CPU
• Явное управление памятью

Способ 5: Развёртывание цикла (Loop unrolling)

Для некоторых алгоритмов можно раскрыть цикл вручную:

// ❌ С циклом
long long sum = 0;
for (int i = 0; i < 1000; ++i) {
    sum += array[i];
}

// ✅ Развёрнутый цикл (processed 4 элемента за итерацию)
long long sum = 0;
for (int i = 0; i < 1000; i += 4) {
    sum += array[i] + array[i+1] + array[i+2] + array[i+3];
}

Это позволяет CPU лучше оптимизировать pipeline.

Способ 6: Trampolining

Для языков без TCO, можно использовать trampolining:

struct Result {
    bool is_final;
    long long value;
};

Result fib_trampoline(int n, int a = 0, int b = 1) {
    if (n == 0) return {true, a};
    return {false, b};  // Не рекурсия!
}

long long fibonacci_trampoline(int n) {
    Result res = {false, 0};
    int a = 0, b = 1;
    
    for (int i = 0; i < n; ++i) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    
    return a;
}

Практический пример: Бинарный поиск

// ❌ Рекурсия
int binary_search_rec(const std::vector<int>& arr, int target, int left, int right) {
    if (left > right) return -1;
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) return mid;
    if (arr[mid] > target) 
        return binary_search_rec(arr, target, left, mid - 1);
    else
        return binary_search_rec(arr, target, mid + 1, right);
}

// ✅ Итерация (идентична рекурсии по скорости, но нет stack overhead)
int binary_search_iter(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    
    return -1;
}

Сравнение производительности

#include <chrono>

int main() {
    // fib(40) - для примера
    
    // Рекурсия: ~1000 мс
    auto start = std::chrono::high_resolution_clock::now();
    int result1 = fibonacci(40);
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Recursion: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << " ms" << std::endl;  // ~1000 ms
    
    // Memoization: < 1 мс
    memo.clear();
    start = std::chrono::high_resolution_clock::now();
    long long result2 = fibonacci_memo(40);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Memoization: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << " ms" << std::endl;  // < 1 ms
    
    // DP: < 1 мкс
    start = std::chrono::high_resolution_clock::now();
    long long result3 = fibonacci_dp(40);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "DP: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() 
              << " µs" << std::endl;  // < 1 µs
}

Когда использовать каждый метод

Правило большого пальца

✅ Сначала - хвостовая рекурсия с TCO (O2/O3) ✅ Если медленно - используй memoization ✅ Если очень медленно - переходи на итерацию ✅ Если критична память - используй DP ✅ Если всё ещё медленно - используй развёртывание цикла

Итог

❌ Простая рекурсия медленная - O(2^n) для перекрывающихся подзадач ✅ Tail-call optimization - компилятор может превратить в цикл ✅ Memoization - ускорение в миллионы раз ✅ Итерация - самый быстрый способ ✅ DP - оптимальное соотношение памяти/скорости