Рекурсія¶

Що таке рекурсія¶

Рекурсія — це прийом програмування, при якому функція викликає сама себе.

Аналогія

Уявіть матрьошку: відкриваєте одну — всередині ще одна, менша. Відкриваєте ту — ще менша. І так далі, поки не дістанетеся найменшої, яку вже не можна відкрити. Ця найменша матрьошка — базовий випадок.

Кожна рекурсивна функція складається з двох обов'язкових частин:

Базовий випадок (base case) — умова, при якій функція зупиняється і повертає результат без рекурсивного виклику
Рекурсивний крок (recursive step) — функція викликає сама себе з меншою або простішою задачею

Без базового випадку рекурсія ніколи не зупиниться — це призведе до помилки переповнення стеку (stack overflow).

Факторіал¶

Математичне визначення¶

Факторіал числа \(n\) визначається так:

\[ n! = \begin{cases} 1, & \text{якщо } n = 0 \\ n \cdot (n-1)!, & \text{якщо } n > 0 \end{cases} \]

Зверніть увагу: визначення посилається само на себе — факторіал \(n\) визначається через факторіал \(n-1\). Це і є рекурсія в математиці.

Наприклад: \(5! = 5 \cdot 4! = 5 \cdot 4 \cdot 3! = 5 \cdot 4 \cdot 3 \cdot 2! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0! = 120\)

Реалізація на C++¶

int factorial(int n) {
    if (n == 0) {
        return 1; // Base case
    }
    return n * factorial(n - 1); // Recursive step
}

Покрокове простеження для factorial(5)¶

flowchart TB
    f5["factorial(5)\nreturn 5 * factorial(4)"]
    f4["factorial(4)\nreturn 4 * factorial(3)"]
    f3["factorial(3)\nreturn 3 * factorial(2)"]
    f2["factorial(2)\nreturn 2 * factorial(1)"]
    f1["factorial(1)\nreturn 1 * factorial(0)"]
    f0["factorial(0)\nreturn 1 ← базовий випадок"]

    f5 --> f4 --> f3 --> f2 --> f1 --> f0

Після досягнення базового випадку результати повертаються у зворотному порядку:

Виклик	Повернення
`factorial(0)`	`1`
`factorial(1)`	`1 * 1 = 1`
`factorial(2)`	`2 * 1 = 2`
`factorial(3)`	`3 * 2 = 6`
`factorial(4)`	`4 * 6 = 24`
`factorial(5)`	`5 * 24 = 120`

Повний приклад¶

#include <iostream>

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

int main() {
    for (int i = 0; i <= 10; ++i) {
        std::cout << i << "! = " << factorial(i) << std::endl;
    }
    return 0;
}

Вивід:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

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

Визначення¶

Послідовність Фібоначчі визначається так:

\[ F(n) = \begin{cases} 0, & \text{якщо } n = 0 \\ 1, & \text{якщо } n = 1 \\ F(n-1) + F(n-2), & \text{якщо } n > 1 \end{cases} \]

Перші числа: \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots\)

Тут два базових випадки (\(n = 0\) і \(n = 1\)) і рекурсивний крок, який посилається на два попередні значення.

Наївна рекурсивна реалізація¶

int fib(int n) {
    if (n == 0) return 0; // Base case 1
    if (n == 1) return 1; // Base case 2
    return fib(n - 1) + fib(n - 2); // Recursive step
}

Дерево викликів для fib(5)¶

Подивимось, що відбувається при виклику fib(5):

flowchart TB
    f5["fib(5)"]
    f4["fib(4)"]
    f3a["fib(3)"]
    f3b["fib(3)"]
    f2a["fib(2)"]
    f2b["fib(2)"]
    f2c["fib(2)"]
    f1a["fib(1)=1"]
    f1b["fib(1)=1"]
    f1c["fib(1)=1"]
    f1d["fib(1)=1"]
    f1e["fib(1)=1"]
    f0a["fib(0)=0"]
    f0b["fib(0)=0"]
    f0c["fib(0)=0"]

    f5 --> f4
    f5 --> f3a
    f4 --> f3b
    f4 --> f2a
    f3a --> f2b
    f3a --> f1a
    f3b --> f2c
    f3b --> f1b
    f2a --> f1c
    f2a --> f0a
    f2b --> f1d
    f2b --> f0b
    f2c --> f1e
    f2c --> f0c

Проблема: повторні обчислення

Зверніть увагу: fib(3) обчислюється двічі, fib(2) — тричі. При більших \(n\) кількість повторних обчислень зростає катастрофічно. Для fib(40) функція виконає понад мільярд викликів! Ми повернемося до цієї проблеми в розділі про мемоізацію.

Стек викликів¶

Як працює рекурсія "під капотом"¶

Коли програма викликає функцію, створюється фрейм (кадр) на стеку викликів (call stack). Фрейм зберігає:

параметри функції
локальні змінні
адресу повернення (куди повернутися після завершення)

При рекурсивному виклику кожен новий виклик додає ще один фрейм на стек. Коли функція завершується, її фрейм знімається зі стеку.

Візуалізація стеку для factorial(4)¶

flowchart LR
    subgraph "Стек росте →"
        direction LR
        s1["main()"]
        s2["main()\nfactorial(4)"]
        s3["main()\nfactorial(4)\nfactorial(3)"]
        s4["main()\nfactorial(4)\nfactorial(3)\nfactorial(2)"]
        s5["main()\nfactorial(4)\n...\nfactorial(1)"]
        s6["main()\nfactorial(4)\n...\nfactorial(0)"]
    end
    s1 --> s2 --> s3 --> s4 --> s5 --> s6

Після того як factorial(0) повертає 1, фрейми починають зніматися зі стеку в зворотному порядку, кожен обчислюючи свій результат.

Stack overflow¶

Стек має обмежений розмір (зазвичай кілька мегабайтів). Якщо рекурсія заглибиться занадто далеко, стек переповниться:

// BAD: no base case — infinite recursion
void infinite() {
    infinite(); // Stack overflow!
}

// BAD: base case never reached
int bad_factorial(int n) {
    return n * bad_factorial(n - 1); // What happens when n < 0?
}

Завжди перевіряйте

Чи є базовий випадок?
Чи наближається кожен рекурсивний виклик до базового випадку?

Якщо хоча б одна умова порушена — програма впаде з помилкою stack overflow.

Рекурсія з масивами¶

Рекурсію можна застосовувати до масивів та нашого vector<T>. Замість циклу ми розбиваємо задачу на: обробити один елемент + рекурсивно обробити решту.

Рекурсивна сума елементів¶

template<typename T>
T recursive_sum(vector<T>& v, int index) {
    if (index >= v.get_size()) {
        return 0; // Base case: no more elements
    }
    return v[index] + recursive_sum(v, index + 1);
}

Виклик: recursive_sum(v, 0) — починаємо з індексу 0.

Для v = {10, 20, 30}:

Виклик	Обчислення
`recursive_sum(v, 0)`	`10 + recursive_sum(v, 1)`
`recursive_sum(v, 1)`	`20 + recursive_sum(v, 2)`
`recursive_sum(v, 2)`	`30 + recursive_sum(v, 3)`
`recursive_sum(v, 3)`	`0` (базовий випадок)

Результат: \(30 + 0 = 30\), потім \(20 + 30 = 50\), потім \(10 + 50 = 60\).

Рекурсивний пошук елемента¶

template<typename T>
int recursive_find(vector<T>& v, T value, int index) {
    if (index >= v.get_size()) {
        return -1; // Base case: not found
    }
    if (v[index] == value) {
        return index; // Base case: found
    }
    return recursive_find(v, value, index + 1);
}

Рекурсивний бінарний пошук¶

Бінарний пошук — класичний приклад рекурсії. Масив повинен бути відсортований:

template<typename T>
int binary_search(vector<T>& v, T value, int left, int right) {
    if (left > right) {
        return -1; // Base case: not found
    }

    int mid = left + (right - left) / 2;

    if (v[mid] == value) {
        return mid; // Base case: found
    }
    if (v[mid] > value) {
        return binary_search(v, value, left, mid - 1); // Search left half
    }
    return binary_search(v, value, mid + 1, right); // Search right half
}

Виклик: binary_search(v, value, 0, v.get_size() - 1).

На кожному кроці розмір задачі зменшується вдвічі — ми відкидаємо половину масиву. Тому бінарний пошук працює за \(O(\log n)\).

Мемоізація¶

Проблема повторних обчислень¶

Повернемось до чисел Фібоначчі. Наївна рекурсія обчислює одні й ті самі значення багаторазово. Кількість викликів зростає експоненціально — приблизно як \(O(2^n)\).

Для fib(40) це понад мільярд викликів. Для fib(50) — програма буде працювати хвилини або навіть години.

Ідея: зберігати обчислені результати¶

Мемоізація (від англ. memoization) — це техніка, при якій ми зберігаємо результати вже обчислених викликів у масиві (кеші). Перед обчисленням перевіряємо: якщо результат вже є в кеші — повертаємо його одразу.

#include <iostream>

const int MAX_N = 100;
long long cache[MAX_N];
bool computed[MAX_N];

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

    if (computed[n]) {
        return cache[n]; // Already computed — return from cache
    }

    cache[n] = fib_memo(n - 1) + fib_memo(n - 2);
    computed[n] = true;
    return cache[n];
}

int main() {
    for (int i = 0; i < MAX_N; ++i) {
        computed[i] = false;
    }

    for (int i = 0; i <= 20; ++i) {
        std::cout << "fib(" << i << ") = " << fib_memo(i) << std::endl;
    }

    return 0;
}

Порівняння¶

	Наївна рекурсія	З мемоізацією
`fib(10)`	177 викликів	19 викликів
`fib(20)`	21 891 виклик	39 викликів
`fib(40)`	~1.6 мільярда	79 викликів
`fib(50)`	~20 мільярдів	99 викликів

Від \(O(2^n)\) до \(O(n)\)

Мемоізація перетворює експоненціальний алгоритм в лінійний: кожне значення fib(k) обчислюється лише один раз, а потім береться з кешу. Загальна кількість обчислень — не більше \(n\).

Рекурсія vs цикл¶

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

int factorial_loop(int n) {
    int result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

А Фібоначчі з мемоізацією — це по суті цикл знизу вгору:

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

    long long prev2 = 0; // fib(0)
    long long prev1 = 1; // fib(1)
    long long current;

    for (int i = 2; i <= n; ++i) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

Коли що використовувати¶

Рекурсія краща	Цикл кращий
Задача природно рекурсивна (дерева, графи, divide and conquer)	Проста ітерація по масиву
Код стає значно читабельнішим	Важлива швидкість і пам'ять (рекурсія витрачає стек)
Глибина рекурсії невелика	Глибина рекурсії може бути великою (ризик stack overflow)

Підсумок¶

Концепція	Що запам'ятати
Рекурсія	Функція викликає сама себе. Обов'язкові: базовий випадок + наближення до нього
Факторіал	Класичний приклад: \(n! = n \cdot (n-1)!\), базовий випадок \(0! = 1\)
Фібоначчі	Два базових випадки, наївна рекурсія — \(O(2^n)\), з мемоізацією — \(O(n)\)
Стек викликів	Кожен виклик — фрейм на стеку. Занадто глибока рекурсія → stack overflow
Мемоізація	Зберігаємо обчислені результати, щоб уникнути повторних обчислень
Рекурсія vs цикл	Будь-яку рекурсію можна переписати циклом. Вибір залежить від задачі

Попередня: Основи шаблонів | Наступна: Оцінка складності алгоритмів | Задачі: Рекурсія