Рекурсия

Функция вызывает себя

Факториал числа n это 1 · 2 · 3 · … · n. Заметим, что факториал n это n, умноженное на факториал n − 1. А факториал 1 просто 1. Так и запишем:

def fact(n):
    if n == 1:
        return 1                # база: ответ известен сразу
    return n * fact(n - 1)      # шаг: сводим к задаче поменьше

print(fact(5))

Как это считается: fact(5) просит fact(4), тот просит fact(3), и так до fact(1), который сразу отвечает 1. Потом ответы возвращаются обратно наверх: 1, 2, 6, 24, 120.

У любой рекурсивной функции две части:

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

Переписываем условие №16

В №16 функцию дают готовой, словами или формулами. Нужно аккуратно перенести её в Python, строчка в строчку. Например:

F(n) = 1 при n ≤ 2; F(n) = F(n − 1) + 2 · F(n − 2) при n > 2.

Чему равно F(20)?

def F(n):
    if n <= 2:
        return 1
    return F(n - 1) + 2 * F(n - 2)

print(F(20))

Каждая строка условия стала строкой кода. Первое условие это база, второе шаг. Если условий больше двух, пишем их через if и elif в том же порядке, что в задаче.

lru_cache: память для функции

Есть проблема. Попробуем числа Фибоначчи: каждое равно сумме двух предыдущих.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(32))

Заметно задумалось. А fib(40) уже не дождёшься. Причина: fib(32) вызывает fib(31) и fib(30), а fib(31) снова вызывает fib(30). Одно и то же считается миллионы раз.

Решение: пусть функция запоминает уже посчитанные ответы. Для этого есть lru_cache. Пишем его строкой над def:

from functools import lru_cache

@lru_cache(None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(32))
print(fib(100))

Мгновенно. Теперь каждое fib(k) считается один раз, а дальше берётся из памяти.

Большие n

В современных №16 часто спрашивают что-то вроде «найдите значение F(2024) / F(2021)». Пробуем:

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    return n * F(n - 1)

print(F(2024) // F(2021))

RecursionError: maximum recursion depth exceeded. Python не даёт функции вызывать себя глубже примерно тысячи раз подряд, а тут нужно больше двух тысяч.

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

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    return n * F(n - 1)

for i in range(1, 2025):     # заполняем память: F(1), F(2), ..., F(2024)
    F(i)

print(F(2024) // F(2021))

Работает, и ответ 2024 · 2023 · 2022.

Сломай код

Нет базы

def F(n):
    return n * F(n - 1)

print(F(5))

RecursionError. Функция вызывает F(4), F(3), F(2), F(1), F(0), F(−1) и дальше без конца, пока Python не остановит. Первое, что проверяешь при этой ошибке: есть ли база и достижима ли она.

База, до которой не дойти

def F(n):
    if n == 0:
        return 1
    return F(n - 2) + 1

print(F(5))

Снова RecursionError. Из 5 через шаг −2 получаются 3, 1, −1, −3… До нуля мы никогда не попадём. В условии №16 база обычно с неравенством, n <= 1, как раз чтобы такого не было. Переписывай знак ровно как в задаче.

Забыли return

def F(n):
    if n == 1:
        return 1
    n * F(n - 1)

print(F(3))

unsupported operand type(s) for *: 'int' and 'NoneType'. Во второй ветке посчитали, но не вернули. Функция без return отдаёт None.

Где пригодится на ЕГЭ

Пример задачи про число программ. Исполнитель умеет прибавлять 1 и умножать на 2. Сколько существует программ, которые превращают 2 в 30?

from functools import lru_cache

@lru_cache(None)
def count(a, b):          # сколько программ из a в b
    if a > b:
        return 0          # перескочили, назад дороги нет
    if a == b:
        return 1          # пришли: одна программа, пустая
    return count(a + 1, b) + count(a * 2, b)

print(count(2, 30))

Тот же шаблон: база (перескочили или пришли) и шаг (сумма по всем командам). В уроке по номеру добавятся условия «проходит через» и «избегает».