4.3. Рекурсия. Декораторы. Генераторы

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

Ключевые вопросы статьи

• Что такое рекурсивные функции и как их правильно составлять?
• Чем отличаются императивный и декларативный стили программирования?
• Почему рекурсивные алгоритмы могут быть медленными — и как это исправить?
• Как работает кеширование с помощью lru_cache?
• Что такое декораторы и как они помогают расширять поведение функций?
• Что такое генераторы и чем они полезны при работе с большими объёмами данных?

Что такое рекурсивные функции и как их правильно составлятьЧто такое рекурсивные функции и как их правильно составлять

Рассмотрим классическую задачу — вычисление факториала числа. В математике факториал обозначается знаком! и определяется так:

Сначала реализуем функцию, которая вычисляет факториал числа n с помощью цикла:

def fact(n):
    factorial = 1
    for i in range(2, n + 1):
        factorial *= i
    return factorial

print(fact(5))

# Вывод программы:
# 120

Теперь перепишем определение факториала немного по-другому:

Это значит, что, чтобы найти n!, мы можем сначала вычислить (n - 1)!, а потом умножить результат на n. Такой способ удобно реализовать с помощью рекурсии.

Рекурсивной называется функция, которая в процессе своей работы вызывает саму себя. Такие функции особенно полезны при работе с задачами, где решение строится на основе более простых подзадач того же типа.

Чтобы правильно составить рекурсивную функцию, нужно выполнить два шага:

1. Задать базовый случай — то, что функция должна вернуть при простейшем значении аргумента.
2. Задать рекурсивное правило — то, как вычислить результат на основе значения функции от меньшего аргумента.

Вот как будет выглядеть рекурсивная реализация вычисления факториала:

def fact(n):
    if n == 0:  # 0! = 1
        return 1
    return fact(n - 1) * n  # n! = (n - 1)! * n

print(fact(5))

# Вывод программы:
# 120

Чем отличаются императивный и декларативный стили программированияЧем отличаются императивный и декларативный стили программирования

Для сравнения, первая версия функции с циклом (for i in range...) относится к императивному стилю. В ней явно указано, как именно нужно последовательно выполнить действия, чтобы получить результат.

Рекурсивные функции ближе к декларативному стилю: они делают код более выразительным и компактным. Однако, как вы увидите дальше, у такого подхода есть свои ограничения — особенно когда речь идёт о производительности.

Почему рекурсивные алгоритмы могут быть медленными — и как это исправитьПочему рекурсивные алгоритмы могут быть медленными — и как это исправить

Рассмотрим применение рекурсивной функции для вычисления n-го числа последовательности Фибоначчи. Это последовательность, в которой:

• первые два числа равны 1;
• каждое последующее — сумма двух предыдущих.

Иными словами:

fib(0) = 1  
fib(1) = 1  
fib(n) = fib(n - 1) + fib(n - 2), если n > 1

На языке Python рекурсивная функция для вычисления n-го числа Фибоначчи может выглядеть так:

def fib(n):
    if n in (0, 1):
        return 1
    return fib(n - 1) + fib(n - 2)

print(fib(35))

# Вывод программы:
# 14930352

Однако при запуске программы вы можете заметить, что вычисление происходит с ощутимой задержкой. Чтобы это измерить, воспользуемся модулем timeit, который позволяет узнать среднее время выполнения фрагмента кода:

from timeit import timeit

def fib(n):
    if n in (0, 1):
        return 1
    return fib(n - 1) + fib(n - 2)

print(f"Среднее время вычисления: "
     f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 3)} с.")

# Вывод программы:
# Среднее время вычисления: 2.924 с.

А теперь сравним с итеративной (императивной) версией той же функции:

from timeit import timeit

def fib(n):
    f_1, f = 1, 1
    for i in range(n - 1):
        f_1, f = f, f_1 + f
    return f

print(f"Среднее время вычисления: "
     f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 3)} с.")

# Вывод программы:
# Среднее время вычисления: 2e-06 с.

Разница огромная: две микросекунды против почти трёх секунд. Почему же рекурсивная функция настолько медленнее?

Причина в том, что при каждом вызове fib(n) функция вызывает саму себя дважды: один раз для fib(n - 1) и один раз для fib(n - 2). Это приводит к тому, что одни и те же значения пересчитываются много раз. Получается ветвящееся рекурсивное дерево, в котором одни и те же подзадачи повторяются снова и снова.

Чтобы наглядно это увидеть, добавим счётчик вызовов функции:

def fib(n):
    global count
    count += 1
    if n in (0, 1):
        return 1
    return fib(n - 1) + fib(n - 2)

count = 0
print(f"35-е число Фибоначчи равно: {fib(35)}.")
print(f"Количество вызовов рекурсивной функции равно: {count}.")

# Вывод программы:
# 35-е число Фибоначчи равно: 14930352.
# Количество вызовов рекурсивной функции равно: 29860703.

Решение — запоминать уже вычисленные значения, чтобы не считать их повторно. Такой приём называется кешированием или мемоизацией.

Один из способов — сохранять промежуточные результаты в словаре:

def fib(n):
    global count
    count += 1
    if n not in cache:
        cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]

count = 0
cache = {0: 1, 1: 1}
print(f"35-е число Фибоначчи равно: {fib(35)}.")
print(f"Количество вызовов рекурсивной функции равно: {count}.")

# Вывод программы:
# 35-е число Фибоначчи равно: 14930352.
# Количество вызовов рекурсивной функции равно: 69.

Теперь попробуем измерить скорость:

from timeit import timeit

def fib(n):
    global count
    count += 1
    if n not in cache:
        cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]

count = 0
cache = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
     f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 6)} с.")

# Вывод программы:
# Среднее время вычисления: 2e-06 с.

Функция работает почти так же быстро, как итеративная, — но при этом остаётся декларативной.

Попробуем теперь вычислить большее число, например fib(1000):

from timeit import timeit

def fib(n):
    if n not in cache:
        cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]

cache = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
     f"{round(timeit('fib(1000)', number=10, globals=globals()) / 10, 6)} с.")

Программа завершится ошибкой:

RecursionError: maximum recursion depth exceeded

В Python по умолчанию глубина рекурсии ограничена (обычно до 1000). Чтобы увеличить лимит, используйте setrecursionlimit из модуля sys:

from timeit import timeit
from sys import setrecursionlimit

def fib(n):
    if n not in cache:
        cache[n] = fib(n - 1) + fib(n - 2)
    return cache[n]

setrecursionlimit(2000)
cache = {0: 1, 1: 1}
print(f"Среднее время вычисления: "
     f"{round(timeit('fib(1000)', number=10, globals=globals()) / 10, 6)} с.")

# Вывод программы:
# Среднее время вычисления: 0.000132 с.

Итак, мы ускорили работу рекурсивного алгоритма с помощью кеширования. Но при этом код стал менее читаемым — появились глобальные переменные и дополнительные проверки. Как сделать то же самое, но проще? В следующем разделе вы узнаете, как поручить кеширование интерпретатору Python с помощью встроенного инструмента — декоратора.

Как работает кеширование с помощью lru_cacheКак работает кеширование с помощью lru_cache

Чтобы не писать дополнительный код вручную, можно поручить кеширование самому интерпретатору. В стандартной библиотеке Python для этого предусмотрен удобный инструмент — декоратор lru_cache из модуля functools.

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

Вот пример использования:

from timeit import timeit
from functools import lru_cache

@lru_cache(maxsize=1000)
def fib(n):
    if n in (0, 1):
        return 1
    return fib(n - 1) + fib(n - 2)
  
print(f"Среднее время вычисления: "
     f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 6)} с.")

# Вывод программы:
# Среднее время вычисления: 2e-06 с.

Как видите, результат сопоставим с кешированием через словарь — но при этом код стал намного чище и короче.

Если вы хотите сбросить кеш или узнать, сколько значений в нём хранится, у lru_cache есть методы .cache_clear() и .cache_info(). Подробнее о них — в документации.

Что такое декораторы и как они помогают расширять поведение функцийЧто такое декораторы и как они помогают расширять поведение функций

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

Декоратор — это специальная конструкция, которая оборачивает функцию и может изменить её поведение до, после или вместо обычного вызова.

В Python уже есть готовые декораторы. Один из них — lru_cache из модуля functools. Он автоматически сохраняет (кеширует) результаты вызова функции, чтобы при повторном вызове с теми же аргументами не пересчитывать результат заново.

Рассмотрим базовый пример:

def func():
    ...

def decorator(old_func):
    def new_func():
        return old_func()
      
    return new_func
  
print(func)
func = decorator(func)
print(func)

Если вы выполните этот код, то увидите, что func превратилась в другую функцию — new_func, обёрнутую в дополнительную логику.

Чтобы не вызывать декоратор вручную, Python предлагает синтаксический сахар — специальную конструкцию с символом @. С её помощью пример выше можно записать так:

def decorator(old_func):
    def new_func():
        return old_func()
      
    return new_func

@decorator
def func():
    ...

Теперь напишем декоратор, который будет считать, сколько раз была вызвана функция, и возвращать это количество вместе с результатом. Такой приём может пригодиться, если вы хотите отладить код или проанализировать его поведение:

# Декоратор принимает функцию f как аргумент
def count(f):
    total = 0

    # Объявляем функцию, которая расширяет функционал f
    def decorated(*args, **kwargs):
        # Переменная total объявлена нелокальной для доступа из внутренней функции
        nonlocal total
        total += 1
       # Возвращаем значение исходной функции и дополнительно total
       return f(*args, **kwargs), total
   # Возвращаем новую функцию как объект
   return decorated

Теперь применим этот декоратор к простой функции hello, которая приветствует пользователя по имени:

@count
def hello(name):
    return f"Привет, {name}!"

print(hello("Пользователь_1"))
print(hello("Пользователь_2"))

Что здесь важно:

• Мы используем ключевое слово nonlocal, чтобы переменная total сохраняла своё значение между вызовами.
• Аргументы *args и **kwargs позволяют оборачивать любую функцию — с любым числом позиционных и именованных параметров.
• Декоратор возвращает новую функцию, которая сначала выполняет дополнительную логику, а затем вызывает оригинальную.

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

Что такое генераторы и чем они полезны при работе с большими объёмами данныхЧто такое генераторы и чем они полезны при работе с большими объёмами данных

В Python функции могут возвращать не только готовое значение, но и генератор — специальный объект, который выдаёт элементы по одному, по запросу. Это особенно удобно, когда вы работаете с большим количеством данных и нет смысла загружать всё в память сразу.

С генераторами вы уже сталкивались, даже если не замечали этого. Например, в выражениях вроде:

squares = (i ** 2 for i in range(10))
print(squares)

# Вывод программы:
# <generator object <genexpr> at 0x000001C225EFC9E0>

Такой объект не содержит все значения сразу — он выдаёт их по одному при каждой итерации. Чтобы получить значение, вызывается метод __next__() (обычно неявно — например, в цикле for).

Чтобы написать свою собственную функцию-генератор, вместо оператора return нужно использовать yield. Этот оператор:

• приостанавливает выполнение функции;
• возвращает текущее значение;
• позволяет продолжить выполнение с того места, где функция остановилась.

Рассмотрим генераторную версию функции Фибоначчи:

def fib(n):
    n_1, n_2 = 1, 1
    for i in range(n):
        yield n_1
        n_1, n_2 = n_2, n_1 + n_2


print(", ".join(str(x) for x in fib(10)))

# Вывод программы:
# 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Также учтите, что в одной функции-генераторе можно использовать несколько операторов yield, как в обычной функции допускается несколько return.

Кроме того, генераторы отлично сочетаются с циклами, выражениями-генераторами и конструкциями вроде map() или filter().

Ещё по темеЕщё по теме

Подробнее о декораторах можно почитать в этом материале.

Что дальшеЧто дальше

Теперь вы умеете создавать рекурсивные функции и понимаете, как они позволяют описывать алгоритмы в декларативном стиле. Вы увидели, почему рекурсивные решения могут быть медленными и как избежать этого с помощью кеширования.

Вы научились использовать декораторы, чтобы расширять поведение функций без изменения их кода. А ещё — познакомились с генераторами и оператором yield, которые позволяют работать с большими объёмами данных эффективно и элегантно.

Дальше мы кратко подведём итоги, вспомним ключевые приёмы работы с функциями и подготовимся к следующей теме: объектной модели Python.

Ключевые выводы статьи

• Рекурсия — это техника, при которой функция вызывает саму себя. Она подходит для задач, определяемых через более простые подзадачи.
• Рекурсивные решения часто наглядны, но могут быть медленными без кеширования.
• Кеширование (мемоизация) позволяет сохранять промежуточные результаты. В Python удобно использовать lru_cache из модуля functools.
• Декораторы позволяют оборачивать функции, добавляя к ним новый функционал — без изменения исходного кода.
• Генераторы создают значения по мере необходимости. Это позволяет экономить память и ускоряет работу с большими объёмами данных.
• Оператор yield делает функцию ленивой: она «замораживается» до следующего вызова и продолжает выполнение с того места, где остановилась.