За счет чего нерекурсивное решение задачи быстрее, чем рекурсивное

Ответ: Overhead вызовов функций и использование стека

Нерекурсивное решение обычно быстрее рекурсивного за счёт eliminating function call overhead и лучшего использования памяти. Это критично для хорошей производительности.

1. Overhead вызовов функций

Что происходит при вызове функции

// ❌ Рекурсивная версия
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Каждый вызов fibonacci() требует:

1. PUSH параметра n в стек
2. CALL инструкция (сохранить адрес возврата)
3. PUSH регистров (калли-сейв)
4. Выполнение функции
5. POP регистров
6. RET (вернуться по сохранённому адресу)

Сборка:

; void call_function():
push rbp              ; сохранить base pointer (8 байт)
mov rbp, rsp         ; установить новый stack frame
sub rsp, 32          ; выделить место для локальных переменных

; ... выполнение функции ...

mov rsp, rbp         ; освободить стек
pop rbp              ; восстановить base pointer
ret                  ; вернуться

Сложность рекурсии

fibonacci(10) разворачивается:
        fib(10)
       /      \
    fib(9)    fib(8)
   /    \      /    \
fib(8) fib(7) fib(7) fib(6)
...

Для fib(40): ~330 миллионов вызовов функций!

Каждый вызов:

• Выделяет новый stack frame
• Инструкции CALL/RET (затраты CPU)
• Кэш-миссы (stack pointer меняется)

2. Stack vs Heap

Рекурсивное решение

int fibonacci(int n) {  // каждый вызов выделяет стек
    // Stack allocation: auto int result;
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Call stack для fib(5):

Дно стека
┌─────────┐
│ main()  │ ← rbp указывает сюда
├─────────┤
│ fib(5)  │
├─────────┤
│ fib(4)  │
├─────────┤
│ fib(3)  │
├─────────┤
│ fib(2)  │
├─────────┤
│ fib(1)  │ ← esp указывает сюда
└─────────┘
Вершина стека

Проблемы:

• Одновременно в памяти столько frame сколько глубина рекурсии
• Stack переполнение при глубокой рекурсии (StackOverflow)
• Memory hierarchy нарушается: промахи кэша

Итеративное решение

int fibonacci(int n) {
    int a = 0, b = 1;  // только 2 переменные на стеке!
    for (int i = 2; i <= n; ++i) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Call stack для iterative fib(5):

┌─────────┐
│ main()  │
├─────────┤
│ fib()   │ ← один frame, не растёт!
│ a, b    │
│ temp    │
└─────────┘

3. Мерсен примеров

Пример 1: Factorial

// ❌ Рекурсивно
int factorial_rec(int n) {
    if (n <= 1) return 1;
    return n * factorial_rec(n - 1);
}

// ✅ Итеративно
int factorial_iter(int n) {
    int result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

Сборка factorial_iter (optimized -O3):

mov eax, 1          ; result = 1
mov ecx, 2          ; i = 2
.L2:
    imul eax, ecx   ; result *= i
    inc ecx          ; i++
    cmp ecx, edi     ; if (i <= n)
    jle .L2
ret

Сборка factorial_rec (optimized):

cmp edi, 1          ; if (n <= 1)
jle .L4
push rbx            ; сохраняем регистр
mov ebx, edi        ; ebx = n
lea edi, [rdi - 1]  ; edi = n - 1
call factorial_rec  ; вызываем рекурсивно
imul eax, ebx       ; rax *= n
pop rbx
ret
.L4:
mov eax, 1
ret

Рекурсивная версия имеет PUSH/POP, CALL, дополнительные операции!

4. Оптимизация компилятором

Tail-call optimization (TCO)

Некоторые компиляторы могут оптимизировать tail-recursive функции:

// Tail-recursive (можно оптимизировать)
int sum_rec(int n, int acc = 0) {
    if (n == 0) return acc;
    return sum_rec(n - 1, acc + n);  // рекурсивный вызов в конце
}

// С флагом -O2 или -O3 компилятор может превратить в цикл
// Но НЕ все компиляторы и НЕ все случаи

Inlining

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

// Маленькая функция
inline int add(int a, int b) {
    return a + b;
}

// После inlining:
int result = a + b;  // функция исчезла, осталась одна инструкция

5. Производительность в реальности

#include <chrono>
#include <iostream>

int fib_rec(int n) {
    if (n <= 1) return n;
    return fib_rec(n - 1) + fib_rec(n - 2);
}

int fib_iter(int n) {
    int a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

int main() {
    auto start = std::chrono::high_resolution_clock::now();
    int result = fib_rec(40);
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Recursive: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>
                 (end - start).count() 
              << " ms" << std::endl;  // ~1000 ms!
    
    start = std::chrono::high_resolution_clock::now();
    result = fib_iter(40);
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Iterative: " 
              << std::chrono::duration_cast<std::chrono::microseconds>
                 (end - start).count() 
              << " µs" << std::endl;  // < 1 µs!
}

Результат (примерно):

Recursive: 1200 ms
Iterative: 0.001 ms  (в миллион раз быстрее!)

Итог

✅ Function call overhead — PUSH/POP, CALL/RET, управление stack frame ✅ Экспоненциальное количество вызовов — O(2^n) calls для простой рекурсии ✅ Stack frame per call — одновременное использование памяти, кэш-промахи ✅ Дублирование вычислений — если нет memoization ⚠️ Tail-call optimization — некоторые компиляторы могут помочь, но не полагайся ⚠️ Memoization — может сделать рекурсию быстрой, но не столько, сколько итерация