def power(base, exponent):
    # Базовый случай
    if exponent == 0:
        return 1
    
    # Рекурсивный шаг
    return base * power(base, exponent - 1)

print(power(2, 3))  # 8 (2 * 2 * 2)

Или определение длины строки без использования встроенных функций.

def string_length(s):
    # Базовый случай: пустая строка
    if s == "":
        return 0
    
    # Рекурсивный шаг: убираем первый символ и считаем остаток
    return 1 + string_length(s[1:])

print(string_length("hello"))  # 5

Работу рекурсивных вызовов удобно визуализировать в виде дерева, где каждый новый вызов порождает ветви, ведущие к базовым случаям, после чего результаты начинают подниматься вверх, к корневому вызову.

Механизм, обеспечивающий возможность таких вложенных вызовов, называется стеком вызовов. Это специальная область памяти, организованная по принципу LIFO ("последним пришёл — первым ушёл"), подобно стопке тарелок. Каждый новый вызов функции помещает в стек свой контекст (аргументы, локальные переменные, место возврата). Когда функция завершает работу, её контекст извлекается из вершины стека, и выполнение продолжается с предыдущего вызова. При глубокой рекурсии стек может исчерпать свой лимит, что приводит к ошибке переполнения стека. Каждый рекурсивный вызов занимает память, поэтому важно, чтобы алгоритм гарантированно сходился к базовому случаю.

Рассмотрим практический вопрос: как написать рекурсивную функцию для вычисления n-го числа Фибоначчи? Последовательность Фибоначчи задаётся правилами: F(0) = 0, F(1) = 1, а для n > 1 каждое число равно сумме двух предыдущих: F(n) = F(n-1) + F(n-2). Это определение напрямую ложится на рекурсивный алгоритм.

def fibonacci(n):
    # Базовые случаи
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Рекурсивный шаг
    return fibonacci(n - 1) + fibonacci(n - 2)

# Примеры
print(fibonacci(0))   # 0
print(fibonacci(1))   # 1
print(fibonacci(5))   # 5
print(fibonacci(10))  # 55

# Почему так медленно?

Посмотрим на дерево вызовов для fibonacci(5):

                    fib(5)
                   /      \
              fib(4)      fib(3)
              /    \      /    \
          fib(3) fib(2) fib(2) fib(1)
          /   \   /  \   /  \
      fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
      /   \
  fib(1) fib(0)

Однако у этой наивной реализации есть серьёзный недостаток — экспоненциальная временная сложность O(2^n). Это происходит из-за колоссального количества повторных вычислений одних и тех же значений, что хорошо видно на дереве вызовов для fibonacci(5), где, например, fibonacci(3) вычисляется несколько раз. Для оптимизации применяют технику мемоизации — сохранения результатов предыдущих вычислений в кеше (словаре), чтобы не считать их заново.

def fibonacci_memo(n, memo={}):
    # Если уже вычисляли, берем из кеша
    if n in memo:
        return memo[n]
    
    # Базовые случаи
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Вычисляем и сохраняем результат
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(50))  # Работает быстро!

С мемоизацией сложность снижается до линейной O(n), поскольку каждое значение вычисляется только один раз.

Это подводит к обсуждению недостатков рекурсивного подхода в сравнении с итеративным (циклы). Главные минусы рекурсии — повышенный расход памяти из-за использования стека вызовов, риск его переполнения при большой глубине, более низкая скорость из-за накладных расходов на вызов функции, а также потенциальная сложность отладки. Итеративные решения обычно более эффективны по памяти и быстродействию для задач, которые можно просто выразить через циклы. Например, вычисление факториала с помощью цикла не требует хранения цепочки вызовов в стеке.