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

Рекурсия

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

0! = 1.
n! = 1 * 2 * ... * n, n > 0.

Напишем функцию, вычисляющую факториал числа n.

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


print(fact(5))

Давайте немного перепишем определение факториала:

0! = 1.
n! = (1 * 2 * ... * (n - 1)) *n = (n - 1)! * n.

Мы видим, что для вычисления n! нам нужно найти (n - 1)! и умножить результат на n. Таким образом, мы используем функцию для вычисления нового значения функции. Функции, в которых происходит вызов самих этих функций, называют рекурсивными.

Давайте напишем рекурсивную функцию для вычисления факториала. При создании рекурсивных функций необходимо:

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

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


print(fact(5))

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

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

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

Первые два числа последовательности равны 1.
n-е число Фибоначчи равно сумме двух предыдущих, то есть fib(n) = fib(n - 1) + fib(n - 2), где n - индекс числа последовательности.

Программа с рекурсивной функцией вычисления n-го числа Фибоначчи запишется так:

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


print(fib(35))

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

14930352

При запуске программы можно заметить, что вычисление 35-го числа последовательности происходит с небольшой задержкой. Проверим, сколько времени занимают вычисления. Выполним их 10 раз и выведем среднее время вычисления с точностью до одной микросекунды. В тестировании скорости работы кода нам помогает стандартный модуль 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 с.

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

Проблема рекурсивной функции заключается в том, что внутри неё происходит два вызова самой себя для каждого значения. И так до тех пор, пока функция не дойдёт до начальных значений аргументов (1 и 1). В итоге появляется несколько рекурсивных веток, которые образуют рекурсивное дерево. Покажем его часть на рисунке.

Числа на схеме показывают номер числа Фибоначчи. Цветом показаны числа с одинаковым номером. Из схемы дерева становится понятно, что рекурсивная реализация функции выполняет много одинаковых вычислений. Давайте добавим счётчик количества вызовов нашей рекурсивной функции:

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 cash:
        cash[n] = fib(n - 1) + fib(n - 2)
    return cash[n]


count = 0
cash = {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 cash:
        cash[n] = fib(n - 1) + fib(n - 2)
    return cash[n]


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

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

Среднее время вычисления: 2e-06 с.

Скорость работы также существенно увеличилась.

Попробуем вычислить число Фибоначчи с номером 1000:

from timeit import timeit


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


cash = {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 cash:
        cash[n] = fib(n - 1) + fib(n - 2)
    return cash[n]


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

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

Среднее время вычисления: 0.000132 с.

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

Итак, наша рекурсивная функция с кешированием стала работать быстро. Однако есть и недостаток: её код стал читаться сложнее. Поручим процесс запоминания промежуточных значений функции интерпретатору. Для этого в Python в стандартном модуле functools есть функция lru_cache. Её следует использовать так, как показано в следующем примере:

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 с.

Благодаря автоматическому кешированию наша функция снова приобрела декларативный вид и при этом работает быстро.

Декораторы

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

Вот принцип работы декоратора:

принимает функцию как аргумент;
объявляет новую функцию, которая расширяет функцию-аргумент;
возвращает новую функцию в качестве объекта.

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

def func():
    ...

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

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

Для того чтобы избежать прямого присвоения функций, в Python используют конструкцию @<имя декоратора, которая автоматически декорирует выбранную функцию. Таким образом пример выше можно переписать:

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

@decorator
def func():
    ...

Напишем декоратор count(), который будет добавлять количество вызовов исходной функции к её результату. Обернём декоратором count() функцию hello(), которая будет принимать в качестве аргумента имя пользователя и возвращать строку с приветствием этого пользователя:

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

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


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


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

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

('Привет, Пользователь_1!', 1)
('Привет, Пользователь_2!', 2)

Во внутренней функции декоратора переменная total объявлена как нелокальная (nonlocal). Это необходимо для получения доступа из функции decorated() к значениям этой переменной, так как total находится вне области видимости внутренней функции.

Также мы указали, что функция decorated() может принимать любое количество позиционных (*args) и именованных (**kwargs) аргументов, чтобы иметь возможность оборачивать функции с любыми аргументами.

Генераторы

Функции в Python могут возвращать в качестве значения объект-генератор. С генераторами мы сталкивались, когда использовали списочные выражения без сохранения значений в список:

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

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

<generator object <genexpr> at 0x000001C225EFC9E0>

Генератор хранит в памяти одно текущее значение и может вернуть следующее, если для него вызывается метод __next__(). Для создания функции-генератора необходимо вместо возврата значения с помощью return использовать оператор yield. Этот оператор приостанавливает работу функции и возвращает значение функции тогда, когда для неё вызывается метод __next__(), например при проходе по значениям генератора в цикле.

Напишем функцию-генератор для последовательности Фибоначчи:

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

Обратите внимание: внутри функции fib() расположен цикл, который должен выполнить n итераций. Однако сами итерации выполняются не все сразу, а по мере необходимости. Запрос на выполнение итераций делает основной код программы, когда требуется следующее значение функции fib(). Другими словами, оператор yield как бы приостанавливает выполнение функции, возвращая текущее значение, и продолжает работу функции, когда требуется получить её следующее значение.
Также следует учитывать, что операторов yield внутри генератора может быть несколько (по аналогии с несколькими return у функций).

Ещё по теме

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

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