Рекурсивные функции

Что проверяет номер

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

Дана функция F(n) (иногда две-три), выраженная через саму себя: есть база и шаг. Спрашивают значение F(N), выражение из значений или «сколько n от 1 до K, для которых F(n) = k».

Простыми словами

Рекурсия похожа на очередь, где каждый спрашивает соседа впереди. Тебе надо узнать F(5), но по формуле для этого нужно знать F(4) и F(3). Те тоже спрашивают дальше, пока вопрос не дойдёт до базы: это случай, где ответ дан прямо в условии, например F(1) = 1. Потом ответы идут обратно по цепочке.

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

Теперь про кэш, или lru_cache. Обычная рекурсия забывчивая: одно и то же F(3) она считает заново каждый раз, когда его спросят. При больших n таких повторов становятся миллионы, и код зависает. Кэш это блокнот: посчитал значение, записал, в следующий раз просто посмотрел.

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

Шаблон из 5 шагов

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

① Переписываем функцию как в условии, условия в том же порядке. ② print(F(26)). ③ Если медленно или слишком глубоко: from functools import lru_cache, перед функцией @lru_cache(None) (пишем перед рекурсией). ④ Прогрев: for n in range(4, 4024): F(n). Левая граница — ограничение (где кончается база), правая — большее число (самое большое нужное n). ⑤ Запасной вариант: import sys, sys.setrecursionlimit(3000).

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + F(n - 1)
    if n > 1 and n % 2 != 0:
        return 2 * F(n - 2)

for n in range(4, 4024):       # прогрев от малого к большому
    F(n)
print(F(26))                   # 4122

Зачем нужен кэш: посчитаем вызовы

Рекурсия без кэша считает одно и то же много раз. Код ниже считает, сколько раз вызвалась функция с кэшем и без него:

from functools import lru_cache

calls = 0
def F(n):
    global calls
    calls += 1
    if n < 3:
        return 1
    return F(n - 1) + 2 * F(n - 2)

print(F(25), calls)

calls = 0
@lru_cache(None)
def G(n):
    global calls
    calls += 1
    if n < 3:
        return 1
    return G(n - 1) + 2 * G(n - 2)

print(G(25), calls)

Ответ один и тот же, а вызовов в тысячи раз меньше. Запусти и сравни сам. Если поднять 25 до 50, первая функция уже не дождётся ответа, а вторая посчитает мгновенно.

# пиши решение здесь

Разбор руками

Возьмём F(n) = 1 при n < 3 и F(n) = F(n − 1) + 2·F(n − 2) при n ≥ 3. Идём снизу вверх:

F(3) = 1 + 2·1 = 3, F(4) = 3 + 2·1 = 5, F(5) = 5 + 2·3 = 11. Рекурсия без кэша считает одни и те же значения снова и снова, поэтому при больших n она зависает. lru_cache запоминает готовые значения.

# пиши решение здесь

Тип 1. Сколько n, для которых F(n) = k

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

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n == 0:
        return 0
    if n > 0 and n % 2 == 0:
        return F(n // 2)            # для целого результата пишем //
    if n % 2 != 0:
        return 1 + F(n - 1)

for n in range(10, 6300):           # прогрев
    F(n)
a = 0
for n in range(1, 501):
    if F(n) == 8:
        a += 1
print(a)                            # 5

# пиши решение здесь

# пиши решение здесь

Тип 2. Две функции

Если функций две, просто напиши обе. Python разрешает им вызывать друг друга, порядок объявления не важен.

from functools import lru_cache

@lru_cache(None)
def F(n):
    return 2 * (g(n - 3) + 8)

@lru_cache(None)
def g(n):
    if n < 10:
        return 2 * n
    if n >= 10:
        return g(n - 8) + 1

for n in range(10, 16000):          # прогрев
    F(n)
print(F(15548))                     # 3936

Второй вариант прогрева: сначала for n in range(40000): g(n), потом for n in reversed(range(40000)): F(n). Иногда нужно ставить else (см. тип 3).

# пиши решение здесь

Тип 3. Большие числа, одна функция

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

Значения огромные, поэтому кэш маленький: lru_cache(100). Работает, если расстояние между нужными числами не больше 100. Нужные значения запоминаем в переменные прямо в цикле, остальные прогреваем в else:

from functools import lru_cache

@lru_cache(100)
def F(n):
    if n < 10:
        return 1
    return (n + 2) * F(n - 2)

for n in range(10, 50004):
    if n == 50003:
        x1 = F(n)
    elif n == 50001:
        x2 = F(n)
    elif n == 49999:
        x3 = F(n)
    else:
        F(n)                        # без else кэш не прогреется
print((x1 // 7 - 11 * x2) // x3)

Деление //, не /: если при обычном / не получается, пиши //.

# пиши решение здесь

Тип 4. Большие числа, две функции

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

Прогрев идёт по направлению зависимостей: функция, которая смотрит вверх (n + 11), греется по убыванию, которая смотрит вниз (n − 8) — по возрастанию.

from functools import lru_cache

@lru_cache(100)
def F(n):
    if n >= 21:
        return F(n - 8) + 900
    if n < 21:
        return 10 * (G(n - 7) - 20)

@lru_cache(100)
def G(n):
    if n >= 15000:
        return n // 17 + 25
    if n < 15000:
        return G(n + 11) - 4

for n in range(15000, 5, -1):       # G смотрит вверх: греем по убыванию
    G(n)
for n in range(21, 401):            # F смотрит вниз: греем по возрастанию
    F(n)
print(F(400))

Тип 5. Три функции

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

Заготовка: три функции под @cache (from functools import *), потом три цикла подряд:

from functools import *

@cache
def F(n):
    ...

@cache
def g(n):
    ...

@cache
def Q(n):
    ...

for n in range(1, 1000000): Q(n)
for n in range(1000000, 1, -1): g(n)
for n in range(1, 1000000): F(n)
print(F(2026))

Порядок и направление циклов зависят от условия: сначала греем функцию, на которую опираются остальные, каждую в своём направлении. @cache и @lru_cache(None) — одно и то же.

Пример: Q(n) = 1 при n ≥ 2500, иначе Q(n + 1) + 3; G(n) = n при n ≤ 3, иначе G(n − 1) + Q(2n) % 7; H(n) = 1 при n ≤ 2, иначе H(n − 1) + G(n) − Q(n) % 4.

from functools import lru_cache

@lru_cache(None)
def Q(n):
    if n >= 2500: return 1
    return Q(n + 1) + 3

@lru_cache(None)
def G(n):
    if n <= 3: return n
    return G(n - 1) + Q(2 * n) % 7

@lru_cache(None)
def H(n):
    if n <= 2: return 1
    return H(n - 1) + G(n) - Q(n) % 4

for n in range(2500, 0, -1): Q(n)       # Q смотрит вверх — по убыванию
for n in range(1, 1501): G(n)
for n in range(1, 1501): H(n)
print(H(1500))

Как решать

Короткий порядок действий на экзамене. Если сомневаешься, какой тип перед тобой, смотри на размер n.

1. Переписываем функцию из условия.
2. Зовёт себя два раза и больше или n большое — ставим @lru_cache(None) и прогреваем циклом.
3. Две-три функции — прогрев по направлению зависимостей.
4. Значения огромные — @lru_cache(100) с else: F(n) в цикле.
5. Деление нацело //.

Ловушки