Рекурсия: база, шаг, стек вызовов

Рекурсия: база и шаг, стек вызовов, классические примеры — факториал, числа Фибоначчи, Ханойские башни.

Рекурсия — это когда функция вызывает саму себя для решения меньшей версии той же задачи. Каждая рекурсивная функция состоит из двух частей: базового случая (когда остановиться) и рекурсивного шага (как уменьшить задачу).

Структура рекурсивной функции

def recursive_func(n):
    # 1. Базовый случай — остановка рекурсии
    if n == 0:
        return 0
    # 2. Рекурсивный шаг — вызываем себя с меньшим аргументом
    return n + recursive_func(n - 1)

print(recursive_func(5))  # 5+4+3+2+1+0 = 15

Вывод:

15

Без базового случая рекурсия не остановится — стек вызовов переполнится (RecursionError). Базовый случай обязателен.

Стек вызовов

Каждый рекурсивный вызов добавляет фрейм в стек вызовов с локальными переменными и точкой возврата. Когда достигнут базовый случай, фреймы «разматываются» обратно.

def factorial(n):
    if n == 0:       # базовый случай
        return 1
    return n * factorial(n - 1)   # рекурсивный шаг

print(factorial(5))   # 5! = 120

Вывод:

120

Стек при вычислении factorial(4):

factorial(4) → 4 * factorial(3)
  factorial(3) → 3 * factorial(2)
    factorial(2) → 2 * factorial(1)
      factorial(1) → 1 * factorial(0)
        factorial(0) → 1      ← база
      → 1 * 1 = 1
    → 2 * 1 = 2
  → 3 * 2 = 6
→ 4 * 6 = 24

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

Классический пример: fib(n) = fib(n-1) + fib(n-2). База — fib(0) = 0, fib(1) = 1.

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

for i in range(8):
    print(f"fib({i}) = {fib(i)}")

Вывод:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13

Эта наивная реализация Фибоначчи — O(2ⁿ) по времени: одно и то же значение вычисляется многократно. Решение — мемоизация (следующая статья).

Ханойские башни

Задача: переместить N дисков со стержня A на стержень C, используя вспомогательный B. Нельзя класть больший диск на меньший.

def hanoi(n, from_rod, to_rod, aux_rod):
    if n == 1:
        print(f"Диск 1: {from_rod} → {to_rod}")
        return
    # Шаг 1: переносим n-1 дисков с from на aux
    hanoi(n - 1, from_rod, aux_rod, to_rod)
    # Шаг 2: переносим самый большой диск
    print(f"Диск {n}: {from_rod} → {to_rod}")
    # Шаг 3: переносим n-1 дисков с aux на to
    hanoi(n - 1, aux_rod, to_rod, from_rod)

hanoi(3, 'A', 'C', 'B')

Вывод:

Диск 1: A → C
Диск 2: A → B
Диск 1: C → B
Диск 3: A → C
Диск 1: B → A
Диск 2: B → C
Диск 1: A → C

Для N дисков нужно ровно 2ⁿ − 1 ходов. Рекурсия идеально описывает это решение.

Коротко

• Рекурсия = базовый случай (остановка) + рекурсивный шаг (уменьшение задачи).
• Каждый вызов занимает фрейм в стеке; глубокая рекурсия грозит переполнением.
• Факториал, Фибоначчи, Ханойские башни — классические рекурсивные задачи.
• Наивный рекурсивный Фибоначчи — O(2ⁿ); мемоизация исправляет это до O(n).