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

Ключевые вопросы параграфа

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

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

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

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

1def fact(n):
2    factorial = 1
3    for i in range(2, n + 1):
4        factorial *= i
5    return factorial
6
7print(fact(5))
8
9# Вывод программы:
10# 120

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

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

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

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

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

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

1def fact(n):
2    if n == 0:  # 0! = 1
3        return 1
4    return fact(n - 1) * n  # n! = (n - 1)! * n
5
6print(fact(5))
7
8# Вывод программы:
9# 120

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

Обратите внимание: рекурсивная версия функции факториала буквально повторяет математическое определение: n! = (n - 1)! × n.
В ней не описан пошаговый процесс вычислений, а задано само правило. Такой подход называется декларативным.

Декларативный стиль программирования описывает, что должно быть получено, а не как этого достичь.

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

Императивный стиль фокусируется на процессе: он отвечает на вопрос «как это сделать?», тогда как декларативный — на «что именно нужно получить?».

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

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

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

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

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

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

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

1def fib(n):
2    if n in (0, 1):
3        return 1
4    return fib(n - 1) + fib(n - 2)
5
6print(fib(35))
7
8# Вывод программы:
9# 14930352

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

1from timeit import timeit
2
3def fib(n):
4    if n in (0, 1):
5        return 1
6    return fib(n - 1) + fib(n - 2)
7
8print(f"Среднее время вычисления: "
9     f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 3)} с.")
10
11# Вывод программы:
12# Среднее время вычисления: 2.924 с.

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

1from timeit import timeit
2
3def fib(n):
4    f_1, f = 1, 1
5    for i in range(n - 1):
6        f_1, f = f, f_1 + f
7    return f
8
9print(f"Среднее время вычисления: "
10     f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 3)} с.")
11
12# Вывод программы:
13# Среднее время вычисления: 2e-06 с.

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

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

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

1def fib(n):
2    global count
3    count += 1
4    if n in (0, 1):
5        return 1
6    return fib(n - 1) + fib(n - 2)
7
8count = 0
9print(f"35-е число Фибоначчи равно: {fib(35)}.")
10print(f"Количество вызовов рекурсивной функции равно: {count}.")
11
12# Вывод программы:
13# 35-е число Фибоначчи равно: 14930352.
14# Количество вызовов рекурсивной функции равно: 29860703.

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

1def fib(n):
2    global count
3    count += 1
4    if n not in cache:
5        cache[n] = fib(n - 1) + fib(n - 2)
6    return cache[n]
7
8count = 0
9cache = {0: 1, 1: 1}
10print(f"35-е число Фибоначчи равно: {fib(35)}.")
11print(f"Количество вызовов рекурсивной функции равно: {count}.")
12
13# Вывод программы:
14# 35-е число Фибоначчи равно: 14930352.
15# Количество вызовов рекурсивной функции равно: 69.

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

1from timeit import timeit
2
3def fib(n):
4    global count
5    count += 1
6    if n not in cache:
7        cache[n] = fib(n - 1) + fib(n - 2)
8    return cache[n]
9
10count = 0
11cache = {0: 1, 1: 1}
12print(f"Среднее время вычисления: "
13     f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 6)} с.")
14
15# Вывод программы:
16# Среднее время вычисления: 2e-06 с.

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

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

1from timeit import timeit
2
3def fib(n):
4    if n not in cache:
5        cache[n] = fib(n - 1) + fib(n - 2)
6    return cache[n]
7
8cache = {0: 1, 1: 1}
9print(f"Среднее время вычисления: "
10     f"{round(timeit('fib(1000)', number=10, globals=globals()) / 10, 6)} с.")

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

RecursionError: maximum recursion depth exceeded

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

1from timeit import timeit
2from sys import setrecursionlimit
3
4def fib(n):
5    if n not in cache:
6        cache[n] = fib(n - 1) + fib(n - 2)
7    return cache[n]
8
9setrecursionlimit(2000)
10cache = {0: 1, 1: 1}
11print(f"Среднее время вычисления: "
12     f"{round(timeit('fib(1000)', number=10, globals=globals()) / 10, 6)} с.")
13
14# Вывод программы:
15# Среднее время вычисления: 0.000132 с.

Обратите внимание: максимально допустимая глубина рекурсии зависит от операционной системы. Увеличивать её можно, но не бесконечно.

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

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

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

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

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

1from timeit import timeit
2from functools import lru_cache
3
4@lru_cache(maxsize=1000)
5def fib(n):
6    if n in (0, 1):
7        return 1
8    return fib(n - 1) + fib(n - 2)
9  
10print(f"Среднее время вычисления: "
11     f"{round(timeit('fib(35)', number=10, globals=globals()) / 10, 6)} с.")
12
13# Вывод программы:
14# Среднее время вычисления: 2e-06 с.

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

Благодаря @lru_cache функция вновь принимает декларативную форму: она просто описывает правило вычисления, а управление памятью и ускорение берёт на себя интерпретатор.

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

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

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

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

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

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

1def func():
2    ...
3
4def decorator(old_func):
5    def new_func():
6        return old_func()
7      
8    return new_func
9  
10print(func)
11func = decorator(func)
12print(func)

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

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

1def decorator(old_func):
2    def new_func():
3        return old_func()
4      
5    return new_func
6
7@decorator
8def func():
9    ...

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

1# Декоратор принимает функцию f как аргумент
2def count(f):
3    total = 0
4
5    # Объявляем функцию, которая расширяет функционал f
6    def decorated(*args, **kwargs):
7        # Переменная total объявлена нелокальной для доступа из внутренней функции
8        nonlocal total
9        total += 1
10       # Возвращаем значение исходной функции и дополнительно total
11       return f(*args, **kwargs), total
12   # Возвращаем новую функцию как объект
13   return decorated

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

1@count
2def hello(name):
3    return f"Привет, {name}!"
4
5print(hello("Пользователь_1"))
6print(hello("Пользователь_2"))

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

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

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

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

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

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

1squares = (i ** 2 for i in range(10))
2print(squares)
3
4# Вывод программы:
5# <generator object <genexpr> at 0x000001C225EFC9E0>

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

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

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

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

1def fib(n):
2    n_1, n_2 = 1, 1
3    for i in range(n):
4        yield n_1
5        n_1, n_2 = n_2, n_1 + n_2
6
7
8print(", ".join(str(x) for x in fib(10)))
9
10# Вывод программы:
11# 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

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

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

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

Ещё по теме

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

✅ Вы разобрались, как работать с рекурсией, декораторами и генераторами?

👉 Оценить этот параграф

Что дальше

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

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

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

А пока вы не ушли дальше — закрепите материал на практике:

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

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

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