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

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

1. 0! = 1.
2. 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))

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

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

Мы видим, что для вычисления 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

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

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

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

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

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


print(fib(35))

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

14930352

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

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

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

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

Ещё по теме

Функция lru_cache в примере используется как декоратор. Подробнее о них можно почитать в этом материале