Рекурсія без страху — Структури даних і алгоритми

Рекурсія — коли функція викликає сама себе, щоб розбити задачу на менші підзадачі. Це зручно для дерев, бектрекінгу і задач «розділяй і володарюй». Головне — знати базовий випадок і не потрапити в нескінченні виклики. Рекурсія схожа на матрьошку: відкриваєте меншу копію задачі, поки не дійдете до найменшої, на яку можна відповісти одразу, потім збираєте відповідь назад.

Коли рекурсія доречна: структура даних природно рекурсивна (бінарне дерево, обхід графа в глибину), потрібно перебрати всі комбінації (підмножини, перестановки), або код коротший і читабельніший за ітерацію. Коли краще цикл: простий лінійний прохід, задачі на кшталт чисел Фібоначчі з повторенням, або коли глибина викликів може перевищити ліміт стека (тисячі рівнів).

Базовий випадок і стек викликів

Базовий випадок — умова, де рекурсія зупиняється і повертає відповідь без нового виклику. Без неї переповнення стека неминуче. Стек викликів зберігає активні виклики: кожен новий рівень «кладеться» зверху, поки не дійдемо до базового випадку, потім розгортання назад. У Python типовий ліміт стека — кілька тисяч викликів; для глибоких дерев краще явний стек у циклі або збільшення ліміту лише локально, якщо знаєте, що робите.

Порада

Перед написанням рекурсивної функції запишіть на папері: 1) який аргумент зменшується; 2) при якому значенні зупиняємось; 3) що повертаємо на базовому випадку; 4) як збираємо результат на шляху назад. Якщо не можете відповісти на четверте питання — рекурсія ще не продумана до кінця.

Приклад

Факторіал: $n! = n \cdot (n-1)!$ , базовий випадок — $0! = 1$ . Для $n=4$ стек викликів: fact(4) → fact(3) → fact(2) → fact(1) → fact(0) → повернення $1, 1, 2, 6, 24$ .

Типовий фрагмент

Каркас рекурсії: базовий випадок і виклик на меншому аргументі.

Python

def product_down_to_one(k):
    if k <= 1:
        return 1
    return k * product_down_to_one(k - 1)

print(product_down_to_one(5))

Вивід

Натисніть «Запустити» — вивід зʼявиться тут

Задача на LeetCode

Спершу розвʼяжіть задачу на LeetCode. Нижче — посилання і розбір українською.

Fibonacci NumberEasy: рекурсія, мемоізація, ітерація

Розбір підходів

Ідея, алгоритм і складність. Код — для читання; здавати розвʼязок треба на LeetCode.

Підхід 1: Рекурсія

Ідея. Прямо з означення: F(n) = F(n−1) + F(n−2), з базою F(0)=0, F(1)=1.

Алгоритм. Якщо N ≤ 1 — повернути N. Інакше повернути fib(N−1) + fib(N−2).

Складність. Час $O(2^N)$ : дерево викликів росте експоненційно. Памʼять $O(N)$ на глибину стека.

Python

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        return self.fib(N - 1) + self.fib(N - 2)

Підхід 2: Знизу вгору (табуляція)

Ідея. Рахуємо всі підзадачі ітеративно й зберігаємо відповіді в масиві, щоб не дублювати роботу.

Алгоритм. Якщо N ≤ 1 — повернути N. Інакше заповнити масив від 2 до N: cache[i] = cache[i−1] + cache[i−2].

Складність. Час $O(N)$ . Памʼять $O(N)$ на масив.

Python

class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        
        cache = [0] * (N + 1)
        cache[1] = 1
        for i in range(2, N + 1):
            cache[i] = cache[i - 1] + cache[i - 2]

        return cache[N]

Підхід 3: Зверху вниз з мемоізацією

Ідея. Рекурсія лишається, але відповідь для кожного k зберігається в словнику й більше не перераховується.

Алгоритм. Словник з 0→0, 1→1. У fib(N): якщо ключ є — повернути його; інакше обчислити й записати.

Складність. Час $O(N)$ . Памʼять $O(N)$ на стек і словник.

Python

class Solution:
    cache = {0: 0, 1: 1}

    def fib(self, N: int) -> int:
        if N in self.cache:
            return self.cache[N]
        self.cache[N] = self.fib(N - 1) + self.fib(N - 2)
        return self.cache[N]

Підхід 4: Ітерація з двома змінними

Ідея. Щоб отримати наступне число Фібоначчі, потрібні лише два попередні — увесь масив зайвий.

Алгоритм. prev2=0, prev1=1. Для i від 2 до N: current = prev1+prev2, зсунути змінні. Повернути current.

Складність. Час $O(N)$ . Памʼять $O(1)$ .

Python

class Solution:
    def fib(self, N: int) -> int:
        if (N <= 1):
            return N

        current = 0
        prev1 = 1
        prev2 = 0

        for i in range(2, N + 1):
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
        return current

Підхід 5: Піднесення матриці до степеня

Ідея. Числа Фібоначчі можна дістати з матричного рівняння; швидке піднесення до степеня дає логарифмічний час.

Алгоритм. Піднести матрицю [[1,1],[1,0]] до степеня N−1 (через половинне піднесення й множення матриць). Відповідь — елемент [0][0].

Складність. Час $O(\log N)$ . Памʼять $O(\log N)$ на стек рекурсії.

Python

class Solution:
    def fib(self, N: int) -> int:
        if (N <= 1):
            return N

        A = [[1, 1], [1, 0]]
        self.matrix_power(A, N - 1)

        return A[0][0]

    def matrix_power(self, A: List[List[int]], N: int):
        if (N <= 1):
            return A

        self.matrix_power(A, N // 2)
        self.multiply(A, A)
        B = [[1, 1], [1, 0]]

        if (N % 2 != 0):
            self.multiply(A, B)

    def multiply(self, A: List[List[int]], B: List[List[int]]) -> None:
        x = A[0][0] * B[0][0] + A[0][1] * B[1][0]
        y = A[0][0] * B[0][1] + A[0][1] * B[1][1]
        z = A[1][0] * B[0][0] + A[1][1] * B[1][0]
        w = A[1][0] * B[0][1] + A[1][1] * B[1][1]

        A[0][0] = x
        A[0][1] = y
        A[1][0] = z
        A[1][1] = w

Підхід 6: Формула Біне

Ідея. Закрита формула через золотий переріз дає F(N) безпосередньо.

Алгоритм. Обчислити round(φ^N / √5), де φ = (1+√5)/2.

Складність. Час $O(\log N)$ через піднесення до степеня. Памʼять $O(1)$ . На великих N можливі похибки float.

Python

class Solution:
    def fib(self, N: int) -> int:
        golden_ratio = (1 + (5 ** 0.5)) / 2
        return int(round((golden_ratio ** N) / (5 ** 0.5)))