Ключевые вопросы параграфа
- Что такое рекурсивные функции и как их правильно составлять?
- Чем отличаются императивный и декларативный стили программирования?
- Почему рекурсивные алгоритмы могут быть медленными — и как это исправить?
- Как работает кеширование с помощью 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. Такой способ удобно реализовать с помощью рекурсии.
Рекурсивной называется функция, которая в процессе своей работы вызывает саму себя. Такие функции особенно полезны при работе с задачами, где решение строится на основе более простых подзадач того же типа.
Чтобы правильно составить рекурсивную функцию, нужно выполнить два шага:
- Задать базовый случай — то, что функция должна вернуть при простейшем значении аргумента.
- Задать рекурсивное правило — то, как вычислить результат на основе значения функции от меньшего аргумента.
Вот как будет выглядеть рекурсивная реализация вычисления факториала:
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
делает функцию ленивой: она «замораживается» до следующего вызова и продолжает выполнение с того места, где остановилась.