infraegeподготовка к ЕГЭ по информатикепростопонятнобесплатно
Проверяем вход
Меню

Рекурсивные алгоритмы

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

Задание 16 · 5 задач

Теория

Вычисляем F(5) по правилу

Последовательность чисел не обязательно перечислять целиком. Можно задать первое значение и правило, по которому из уже известного получается следующее. Такую запись называют рекуррентным определением. Здесь F(n) — значение с номером n.

Пусть первое значение равно F(1) = 1, а каждое следующее получается по правилу F(n) = 2·F(n − 1) + 1 при n > 1. Формула сама по себе ничего не считает — чтобы найти F(n), сначала нужно знать F(n − 1). Найдём F(5), поднимаясь от того, что уже известно.

Разберём на примере
Найдите F(5), если F(1) = 1 и F(n) = 2·F(n − 1) + 1
Каждое следующее значение выражается через предыдущее — начнём с того, что уже дано, и будем подниматься вверх.
  1. F(1) = 1 — это значение дано, вычислять его не нужно.
  2. F(2) = 2·F(1) + 1 = 2·1 + 1 = 3.
  3. F(3) = 2·F(2) + 1 = 2·3 + 1 = 7.
  4. F(4) = 2·F(3) + 1 = 2·7 + 1 = 15.
  5. F(5) = 2·F(4) + 1 = 2·15 + 1 = 31.

Зачем нужны база и шаг

В первом примере мы использовали две части определения. Первая — начальное значение, от которого можно начать вычисления. Его называют базовым случаем: F(1) = 1 просто дано, вычислять его не нужно. Вторая часть — правило перехода: F(n) = 2·F(n − 1) + 1 при n > 1, которое показывает, как получить следующее значение из предыдущего.

Посмотрим, как обе части работают вместе. Чтобы найти F(5), правило требует F(4), для него нужно F(3), и так далее: вопросы идут вниз. Они останавливаются на F(1) — это значение дано. С него ответы поднимаются вверх: из каждого найденного значения получается следующее.

Вопросы идут от F(5) вниз, пока не встретится известное значение F(1) = 1. Оттуда ответы поднимаются вверх: F(2) = 3, F(3) = 7, F(4) = 15, F(5) = 31.

Теперь уберём базу. Если в определении нет значения F(1), то вопрос «чему равно F(1)?» тоже требует предыдущего значения F(0), затем F(-1) и так без конца. Это как ряд костяшек домино: без первого толчка (без базового случая) ни одна костяшка не упадёт.

Без базы вопросы не останавливаются: для F(1) нужно F(0), для F(0) — F(-1) и так дальше, ни одного значения найти не удастся.

С базой определение не ходит по кругу: вопросы упираются в известное значение, а дальше каждое значение опирается только на уже найденное — из F(1) однозначно получается F(2), из него — F(3), и так для любого n. Это тот же принцип, что у математической индукции: база плюс шаг, работающий для каждого n. Важно, чтобы аргумент на каждом шаге приближался к базе — тогда цепочка обязательно закончится.

Рекурсивная функция и стек вызовов

Пока мы поднимались от базового значения вручную. Ту же цепочку можно поручить Python. Функцию, которая во время вычисления вызывает саму себя, называют рекурсивной. Как устроены аргументы и return, разобрано в уроке курса «Функции», а как вызовы уходят вглубь и возвращаются — в уроке «Рекурсия».

def F(n):    if n == 1:        return 1  # Базовый случай: значение уже известно    return 2 * F(n - 1) + 1  # Шаг: сначала находим F(n - 1) print(F(5))

Чтобы увидеть, что происходит при вызове F(4), добавим печать до и после рекурсивного вызова:

def F(n):    print("вызов", n)    if n == 1:        print("база", n)        return 1    result = 2 * F(n - 1) + 1    print("возврат", n, "->", result)    return result F(4) # Программа напечатает:# вызов 4# вызов 3# вызов 2# вызов 1# база 1# возврат 2 -> 3# возврат 3 -> 7# возврат 4 -> 15

Сначала вызовы уходят вглубь — 4, 3, 2, 1 — пока не будет достигнут базовый случай. Пока это не произошло, каждый вызов приостановлен и ждёт результата вложенного вызова: Python хранит такие ожидающие вызовы в стеке вызовов. После базы значения возвращаются в обратном порядке — 2, 3, 4 — и каждый вызов завершается, получив нужное число. В строке result = 2 * F(n - 1) + 1 выражение F(n - 1) — уже не запись, а конкретное число, которое вернул вложенный вызов.

стопка ожидающих вызовов F(4), F(3), F(2), F(1)
Вызовы уходят вверх, пока не дойдут до базы F(1) = 1, а ожидающие ждут в стопке. Ответы возвращаются вниз: 1, 3, 7, и F(4) = 15.

У стека есть предел: по умолчанию Python допускает около 1000 вложенных вызовов. Для функции F(n) = n·F(n − 1) вызов F(2024) — это цепочка из двух тысяч ожидающих вызовов, и она не помещается:

def F(n):    if n == 1:        return 1    return n * F(n - 1) print(F(2024))  # RecursionError: превышена глубина рекурсии

Один из способов — поднять лимит на длину цепочки с небольшим запасом:

import sys # Глубина цепочки 2024, лимит чуть большеsys.setrecursionlimit(5000) def F(n):    if n == 1:        return 1    return n * F(n - 1) print(F(2024) // F(2022))  # 4094552

Это только один инструмент из нескольких. Следующие разделы показывают другие способы — цикл, кеш, прогрев кеша — и объясняют, когда какой выбирать.

Цикл: одно значение вместо стека

Когда каждое значение зависит только от предыдущего, стек не нужен вовсе: в каждый момент достаточно помнить последнее найденное значение. Цикл перезаписывает одну переменную и не откладывает вызовы:

f = 1  # Начинаем с известного F(1) for n in range(2, 2025):    f = n * f  # Новое значение заменяет предыдущее print(f) # Общий шаблон для одного предыдущего значения:#   f = базовое_значение#   for n in range(первое_n, target + 1):#       f = ...  # формула через предыдущее значение f#   print(f)

Цикл — не «более правильный» способ, а другой инструмент. Он хорошо подходит для линейной цепочки, где шаг всегда «предыдущее значение → следующее». Если аргумент перепрыгивает (n / 2, n + 4) или значение зависит от условия, цепочку проще записать рекурсией — так мы и будем делать дальше.

Разберём на примере
Найдите F(5), если F(1) = 2 и F(n) = 3·F(n − 1) − 1
Проследим, что хранит переменная f после каждого шага цикла — так проверяют цикл на малых значениях.
  1. Перед циклом f = 2 — это F(1).
  2. n = 2: f = 3·2 − 1 = 5.
  3. n = 3: f = 3·5 − 1 = 14.
  4. n = 4: f = 3·14 − 1 = 41.
  5. n = 5: f = 3·41 − 1 = 122 — это и есть F(5).
f = 2 for n in range(2, 6):  # 6: граница range не включается    f = 3 * f - 1 print(f)  # 122

Когда нужны два предыдущих значения

До сих пор для нового значения хватало одного предыдущего. Но иногда формула зависит сразу от двух: F(n) = F(n − 1) + F(n − 2). Тогда одного базового значения недостаточно — уже для F(3) нужны сразу F(2) и F(1), поэтому определение обязано задать оба сразу: F(1) = 2, F(2) = 3.

Самый известный пример — числа Фибоначчи: F(1) = F(2) = 1 и F(n) = F(n − 1) + F(n − 2), то есть 1, 1, 2, 3, 5, 8, … Если формула берёт три предыдущих значения, нужно три базовых. Например, при 1, 1, 2 и сумме трёх предыдущих получается 1, 1, 2, 4, 7, 13, 24 — это числа трибоначчи. В задачах базовые значения могут быть другими: их всегда берут из условия, а не из памяти о «стандартной» последовательности.

Разберём на примере
Найдите F(6), если F(1) = 2, F(2) = 3 и F(n) = F(n − 1) + F(n − 2)
Как и раньше, поднимаемся от известных значений вверх — только теперь на каждом шаге нужно держать в уме два последних числа, а не одно.
  1. F(3) = F(2) + F(1) = 3 + 2 = 5.
  2. F(4) = F(3) + F(2) = 5 + 3 = 8.
  3. F(5) = F(4) + F(3) = 8 + 5 = 13.
  4. F(6) = F(5) + F(4) = 13 + 8 = 21.

Повторные вызовы и кеш

Для зависимости от одного значения главной опасностью была глубина стека. У рекурсивной функции с двумя предыдущими значениями появляется другая проблема. Возьмём числа Фибоначчи, запишем их рекурсивно и выпишем, какие вызовы порождает F(5):

def F(n):    if n <= 2:        return 1    return F(n - 1) + F(n - 2) # Вызовы, которые порождает F(5):# F(5)# ├─ F(4)# │  ├─ F(3)# │  │  ├─ F(2)# │  │  └─ F(1)# │  └─ F(2)# └─ F(3)#    ├─ F(2)#    └─ F(1)

В дереве вызовов F(3) вычисляется дважды, а F(2) — трижды: одно и то же значение считается заново, хотя уже было найдено.

Дерево вызовов F(5): значение F(3) вычисляется дважды, F(2) — трижды. Два поддерева с F(3) обведены штриховыми рамками.

Измерим, насколько это плохо. Будем считать, сколько раз вычисляется F(3):

count = 0 def F(n):    global count    if n == 3:        count += 1  # Считаем повторы F(3)    if n <= 2:        return 1    return F(n - 1) + F(n - 2) for n in (10, 15, 20, 25):    count = 0    F(n)    print(n, count) # Программа напечатает:# 10 21# 15 233# 20 2584# 25 28657

Число повторов растёт так же быстро, как сами числа Фибоначчи. Для F(40) такая программа делает больше двухсот миллионов вызовов — работа занимает минуты, хотя ответ можно получить за сорок шагов. Идея исправления очевидна: один раз вычислить значение и запомнить его. Это называют кешированием, а в Python его берёт на себя декоратор lru_cache из модуля functools — отметка перед функцией:

from functools import lru_cache @lru_cache(None)def F(n):    if n <= 2:        return 1    return F(n - 1) + F(n - 2) print(F(40))  # 102334155 — мгновенно

Теперь каждое значение вычисляется один раз, а при повторном обращении берётся из памяти. Сравните деревья вызовов без кеша и с кешем:

дерево вызовов F(5) без кеша и с кешем
Без кеша F(5) порождает 9 вызовов, и четыре из них повторяют уже найденное (оранжевые). С кешем настоящих вызовов 5: повторы заменены ответом из кеша.

Аргумент None — «не ограничивать размер кеша». Если написать @lru_cache() без аргумента, Python по умолчанию запомнит лишь 128 последних значений, а более старые забудет, и часть работы снова будет повторяться. (Начиная с Python 3.9 есть краткая запись @cache — то же самое, что lru_cache(None); запись с None работает везде.)

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

# Способ 1: список, индекс — это аргументtarget = 6F = [0] * (target + 1) # Два базовых значения нужны до первого шагаF[1] = 2F[2] = 3 for n in range(3, target + 1):    F[n] = F[n - 1] + F[n - 2]  # Сохраняем один раз print(F[target]) # Способ 2: две переменные вместо спискаf_prev2, f_prev1 = 2, 3 for n in range(3, 7):    # Правая часть берёт оба старых значения    f_prev2, f_prev1 = f_prev1, f_prev1 + f_prev2 print(f_prev1)
Неверно
Чтобы сдвинуть два хранимых значения на шаг вперёд, можно просто присвоить f_prev2 = f_prev1, а потом f_prev1 = f_prev1 + f_prev2 — порядок не важен.
Как правильно
Порядок важен: после первой строки f_prev2 уже стало равно старому f_prev1, поэтому вторая строка складывает f_prev1 само с собой, а не с настоящим предыдущим значением. Сначала нужно вычислить новое значение в отдельную переменную и только потом обновить обе хранимых: f_current = f_prev1 + f_prev2; f_prev2 = f_prev1; f_prev1 = f_current.

Шаг не на 1: деление аргумента

До сих пор аргумент уменьшался на 1 или на 2. В заданиях часто встречается другой шаг: аргумент делится, например на 10 или на 2. Тогда даже огромное число, вроде 10³⁰, доходит до базового случая за несколько десятков вызовов. Для такой записи нужны две операции. Оператор // — деление нацело, оператор % — остаток. Для 472: 472 // 10 равно 47 (число без последней цифры), а 472 % 10 равно 2 (последняя цифра).

Пусть F(n) = n при n < 10, а при n ≥ 10 значение равно n%10 + 2·F(n//10): последняя цифра плюс удвоенное значение для числа без неё.

from functools import lru_cache @lru_cache(None)def F(n):    if n < 10:        return n    return n % 10 + 2 * F(n // 10) print(F(472))       # 32print(F(10 ** 30))  # 1073741824

Цепочка для 10³⁰ — это всего 31 вызов, поэтому ни цикл «от 1 до n», ни увеличение лимита здесь не нужны: аргумент уменьшается в десять раз на каждом шаге.

Разберём на примере
Найдите F(472), если F(n) = n при n < 10 и F(n) = n%10 + 2·F(n//10) при n ≥ 10
Сначала спускаемся к базовому случаю, отрезая по одной цифре, а затем поднимаемся и подставляем найденные значения.
  1. 472 ≥ 10, поэтому F(472) = 472%10 + 2·F(47) = 2 + 2·F(47).
  2. 47 ≥ 10: F(47) = 7 + 2·F(4).
  3. 4 < 10 — базовый случай: F(4) = 4.
  4. Поднимаемся: F(47) = 7 + 2·4 = 15, затем F(472) = 2 + 2·15 = 32.
Неверно
Вместо n // 10 можно писать n / 10 — в Python это одно и то же, разница только в записи.
Как правильно
Это разные операции. Обычное деление / всегда возвращает дробное число: 472 / 10 даёт 47.2, а даже 9 / 3 — 3.0. Для огромных чисел хуже: 10 ** 30 / 10 — это уже приближённое 1e+29, и часть цифр потеряна. Если в задании аргумент должен остаться целым, берут //.

Разные правила для чётных и нечётных

В заданиях формула часто зависит от условия на аргумент: свои правила для чётных и нечётных n, для разных диапазонов. Тогда функция состоит из нескольких веток, и для каждого n нужно сначала выбрать подходящую. Условие «чётное» записывают как n % 2 == 0: остаток от деления на 2 равен нулю.

Рассмотрим функцию: F(1) = 1; F(n) = F(n/2) + 3, если n > 1 и n чётно; F(n) = F(n − 1) + 1, если n > 1 и n нечётно. Здесь при чётном n значение n/2 — целое, поэтому в программе пишут n // 2. Вручную такую цепочку удобнее разворачивать сверху вниз: записывать, какая ветка применяется на каждом шаге, а затем подниматься.

Для F(21) вопросы идут вниз по чётности: 21 нечётно, берём n-1, а 20 и 10 чётны, делим пополам, и так до базы F(1) = 1. Ответы поднимаются с добавками +3 для чётных и +1 для нечётных: 4, 7, 8, 11, 14, 15.
Разберём на примере
Найдите F(21), если F(1) = 1, F(n) = F(n/2) + 3 при чётном n > 1 и F(n) = F(n − 1) + 1 при нечётном n > 1
На каждом шаге сначала определяем чётность аргумента и выбираем ветку. Так спускаемся до F(1), затем поднимаемся.
  1. 21 нечётно: F(21) = F(20) + 1.
  2. 20 чётно: F(20) = F(10) + 3; затем 10 чётно: F(10) = F(5) + 3.
  3. 5 нечётно: F(5) = F(4) + 1; затем 4 чётно: F(4) = F(2) + 3, а F(2) = F(1) + 3.
  4. F(1) = 1 — базовый случай. Поднимаемся: F(2) = 4, F(4) = 7, F(5) = 8, F(10) = 11, F(20) = 14.
  5. F(21) = F(20) + 1 = 15.
from functools import lru_cache @lru_cache(None)def F(n):    if n == 1:        return 1  # База проверяется первой    if n % 2 == 0:        return F(n // 2) + 3    return F(n - 1) + 1 print(F(21))  # 15 — совпало с ручным счётом
Неверно
Порядок проверок в if неважен: можно сначала разобрать чётность, а базовый случай n == 1 проверить в конце.
Как правильно
Порядок важен. Число 1 нечётно, поэтому оно попадёт в ветку F(0) + 1, затем 0 чётно и F(0) вызовет F(0 // 2) — то есть снова F(0), и цепочка никогда не достигнет базы. Базовые случаи проверяют первыми, а условия веток записывают в том порядке, как они даны в задаче.

Рекурсия «вверх» и прогрев кеша

Иногда значение выражается не через меньшие аргументы, а через большие: F(n) = F(n + 4) + 2 при n < 4200, а база задана сверху — F(n) = 7 при n ≥ 4200. Аргумент растёт до тех пор, пока не достигнет базы, поэтому цепочка идёт «вверх». Значит, считать «снизу вверх от F(1)» здесь нельзя: считать нужно от базы вниз к запрошенному аргументу.

Цепочка от F(100) до базы — больше тысячи вызовов, и обычная рекурсия упрётся в лимит. Кеш здесь не спасает: пока не дошли до базы, ничего не посчитано и запоминать нечего. Выход — «прогреть кеш»: заранее вызвать функцию для подходящих аргументов в таком порядке, чтобы каждый вызов опирался на уже запомненное значение. Порядок выбирают против направления зависимости: раз F(n) нуждается в F(n + 4), идём от больших n к малым. Верхняя граница прогрева — первое значение, попадающее в базу. Если бы функция зависела от F(n − 1), порядок был бы обратным: от малых к большим.

числовая ось n: стрелки зависимости вправо, прогрев кеша справа налево
Стрелки зависимости идут вправо, от n к n + 4, поэтому кеш прогревают справа налево, начиная с базы n ≥ 4200. От F(100) до базы 1025 шагов, больше лимита 1000.
Разберём на примере
Найдите F(100) и F(100) − F(96), если F(n) = 7 при n ≥ 4200 и F(n) = F(n + 4) + 2 при n < 4200
Сначала подумаем, нельзя ли обойтись без программы: разность соседних значений часто упрощается. Затем проверим ответ вторым способом — кодом с прогревом кеша.
  1. Формула связывает F(96) = F(100) + 2, поэтому F(100) − F(96) = −2 без вычисления самих значений.
  2. Чтобы найти F(100), нужно подняться от 100 до 4200 с шагом 4: это (4200 − 100) / 4 = 1025 шагов, каждый добавляет 2, а в базе 7.
  3. F(100) = 7 + 2·1025 = 2057, а F(96) = 2059.
  4. Проверяем программой. Цепочка из 1025 вызовов длиннее стандартного лимита, поэтому сначала заполняем кеш от больших n к малым — так каждый вызов сразу берёт результат из кеша.
from functools import lru_cache @lru_cache(None)def F(n):    if n >= 4200:        return 7    return F(n + 4) + 2 # F(n) требует F(n + 4): идём от больших n к малымfor n in range(4200, 95, -1):    F(n) print(F(100), F(100) - F(96))  # 2057 -2

Две связанные функции F и G

В некоторых заданиях определены сразу две функции, и каждая может вызывать другую: например, F(n) = F(n − 1) + G(n − 2) и G(n) = G(n − 1) + F(n − 1). Идея решения не меняется: ищем базовые значения обеих функций, понимаем, от каких значений зависит каждая, и поднимаемся. Удобно вести таблицу с двумя столбцами — строка для каждого n. В программе обе функции получают свой @lru_cache(None).

Каждая ячейка считается по двум уже найденным: F(n) по F(n-1) из своего столбца и G(n-2) из соседнего, G(n) по G(n-1) и F(n-1). Так строка за строкой получается F(8) = 44.
Разберём на примере
Найдите F(8), если
F(n) = 1, G(n) = 2 при n ≤ 2,
а при n > 2: F(n) = F(n − 1) + G(n − 2),
G(n) = G(n − 1) + F(n − 1)
Заполняем таблицу по строкам: для каждого n сначала F(n), потом G(n), используя уже найденные строки выше.
  1. n = 1, 2: базовые значения даны, F = 1 и G = 2. Это первые две строки таблицы.
  2. n = 3: F(3) = F(2) + G(1) = 1 + 2 = 3; G(3) = G(2) + F(2) = 2 + 1 = 3. Каждая функция берёт одно значение из своего столбца и одно из соседнего.
  3. Остальные строки считаются так же по уже заполненным: сначала F(n), потом G(n). Вся таблица ниже.
  4. Ответ стоит в строке n = 8 столбца F: F(8) = 44.
from functools import lru_cache @lru_cache(None)def F(n):    if n <= 2:        return 1    return F(n - 1) + G(n - 2) @lru_cache(None)def G(n):    if n <= 2:        return 2    return G(n - 1) + F(n - 1) # Значения, которые считает программа:#   n       1   2   3   4   5   6   7   8#   F(n)    1   1   3   5   8  14  25  44#   G(n)    2   2   3   6  11  19  33  58print(F(8))   # 44 — совпало с таблицейprint(F(10))  # 135
Неверно
Раз F вызывает G, то функцию G обязательно нужно определить раньше F.
Как правильно
Нет: имя G ищется в момент вызова, а не в момент записи def F. Достаточно, чтобы к первому вызову обе функции уже существовали: сначала обе def (каждая со своим декоратором), потом print. Ошибка NameError появляется, если вызвать F(...) выше определения G.

Сколько n удовлетворяют условию

В части заданий спрашивают не значение, а количество аргументов: «сколько существует n от 1 до 500, для которых F(n) = 16». Здесь функция вызывается для каждого n по очереди, поэтому без кеша работа умножилась бы на число проверок, а с общим кешем каждое значение считается один раз. Общий шаблон: цикл по аргументам, условие на значение и счётчик. Перед тем как считать сотни значений, полезно вывести первые несколько и сверить их с ручным счётом — так проверяется сама функция.

Разберём на примере
Сколько существует n, таких что 1 ≤ n ≤ 500 и F(n) = 16, если F задана как в разделе о чётных и нечётных значениях
Функция та же: F(1) = 1, F(n/2) + 3 для чётных, F(n − 1) + 1 для нечётных. Сначала проверим программу на малых n, потом посчитаем количество.
  1. Первые значения F(1), …, F(12): 1, 4, 5, 7, 8, 8, 9, 10, 11, 11, 12, 11. Их можно проверить вручную, так же как мы проверили F(21) = 15.
  2. Перебираем n от 1 до 500 включительно и считаем случаи, где F(n) == 16.
  3. Подходят 23, 27, 29, 30, 32 — всего 5. Для контроля проверим n = 30 вручную: F(3) = 5, F(6) = 8, F(7) = 9, F(14) = 12, F(15) = 13, F(30) = 16.
count = 0for n in range(1, 501):  # 501: 500 должно войти в перебор    if F(n) == 16:        count += 1 print(count)  # 5print([n for n in range(1, 501) if F(n) == 16])# [23, 27, 29, 30, 32]

Большие n: сокращаем, а не считаем

До этого нам было нужно само значение функции, поэтому мы шли от базы до нужного аргумента. Но если аргумент огромный — 2024, 100 000 — а нужен не сам F(n), а отношение или разность двух соседних значений, считать всю последовательность необязательно. Обычно достаточно раскрыть только несколько последних шагов и что-то сократить. Методические рекомендации ФИПИ к заданию 16 советуют именно это: сначала проанализировать выражение на предмет упрощения, а не сразу писать программу — для N!/(N − 1)! факториалы вычислять не нужно. Если в выражении несколько значений функции, например (F(100) + 3·F(99)) / F(98), все они выражаются через самое «маленькое» из них, F(98), после чего общий множитель выносится и сокращается: (100·99·F(98) + 3·99·F(98)) / F(98) = 9900 + 297 = 10197.

сокращение F(100) на F(98): два шага, два множителя
Между F(98) и F(100) два шага, поэтому F(100) = 100·99·F(98). Общий множитель F(98) сокращается, остаётся 100·99 = 9900.
Разберём на примере
Найдите F(100) / F(98), если F(1) = 2 и F(n) = n·F(n − 1)
Выразим F(100) и F(99) через F(98) — до него раскрывать не нужно.
  1. F(99) = 99·F(98).
  2. F(100) = 100·F(99) = 100·99·F(98).
  3. F(100) / F(98) = 100·99·F(98) / F(98) = 100·99 = 9900.

Разность значений и когда сокращение не работает

Если формула складывает, а не умножает, сокращается разность, а не отношение. Для F(n) = F(n − 1) + 2n + 3 каждое значение отличается от предыдущего на 2n + 3, поэтому F(n) − F(n − k) — сумма k таких добавок. Когда слагаемых много, их складывают как арифметическую прогрессию: количество слагаемых умножить на полусумму первого и последнего.

Не всякая формула сокращается «нацело». Пусть F(1) = 1, F(n) = n·F(n − 1) − 1. Раскроем три шага: F(200) = 200·F(199) − 1, затем F(199) = 199·F(198) − 1, затем F(198) = 198·F(197) − 1. После подстановки F(200) = 200·199·198·F(197) − 200·199 − 200 − 1 = 7 880 400·F(197) − 40 001. Значит, F(200) / F(197) = 7 880 400 − 40 001 / F(197). Значение F(197) огромно, поэтому вычитаемая дробь больше нуля, но меньше единицы, и число чуть меньше 7 880 400: его целая часть равна 7 880 399. Если задание просит «целую часть», оценка такого вида — законный способ, а если формула сокращается точно, как в предыдущем разделе, целая часть не нужна.

Разберём на примере
Найдите F(1000) − F(997), если F(1) = 5 и F(n) = F(n − 1) + 2n + 3
Разность через три шага — это сумма трёх добавок. Затем проверим результат программой: если два способа дают одно и то же число, ошибки в рассуждении почти нет.
  1. F(1000) = F(999) + 2·1000 + 3 = F(999) + 2003.
  2. F(999) = F(998) + 2001 и F(998) = F(997) + 1999.
  3. F(1000) − F(997) = 2003 + 2001 + 1999 = 6003. Базовое значение F(1) в ответ не вошло.
  4. Проверка вторым способом: программа с циклом (значение зависит от предыдущего) даёт то же число.
f = {1: 5}for n in range(2, 1001):  # 1001: включаем n = 1000    f[n] = f[n - 1] + 2 * n + 3 print(f[1000] - f[997])  # 6003
Неверно
Для F(n) = n·F(n − 1) − 1 отношение F(200) / F(197) сокращается так же, как для n·F(n − 1), и равно 200·199·198 = 7 880 400.
Как правильно
Слагаемое −1 при каждом умножении накапливается: в разложении остаётся − 40 001. Точно сократить F(197) не получится, и отношение не равно 7 880 400, а чуть меньше. Поэтому в таких заданиях просят целую часть, а рассуждение строят через оценку поправки.

Шаблон программы для задания 16

Соберём выученное в шаблон программы. Каждая строка отвечает на конкретную проблему, которую мы уже видели:

import sysfrom functools import lru_cache # Если цепочка вызовов длиннее 1000sys.setrecursionlimit(10000) @lru_cache(None)  # Значение считается один разdef F(n):    if n <= 3:  # База проверяется первой        return ...    if n % 2 == 0:  # Ветви в порядке условия        return ...    return ... # Прогрев кеша, если цепочка слишком длинная:# for n in range(...): F(n)print(F(...))

Из шаблона не нужно брать всё сразу. Импорт sys и setrecursionlimit нужны только при длинной цепочке; прогрев кеша — при рекурсии вверх или очень длинной цепочке; кеш — почти всегда, когда есть два и более рекурсивных вызова. И перед тем как отдавать ответ, программу проверяют на малом значении, которое можно посчитать вручную.

Разберём на примере
Найдите F(60), если F(n) = 2 при n ≤ 3, F(n) = F(n − 1) + F(n − 3) при чётном n > 3 и F(n) = F(n − 2) + n при нечётном n > 3
Переводим условие в программу по порядку и проверяем на малом значении, посчитанном руками.
  1. База: n ≤ 3 — значение 2. Ветви: чётное n и нечётное n.
  2. Ручная проверка: F(4) = F(3) + F(1) = 4, F(5) = F(3) + 5 = 7, F(6) = F(5) + F(3) = 9, F(7) = F(5) + 7 = 14, F(8) = F(7) + F(5) = 21, F(9) = F(7) + 9 = 23, F(10) = F(9) + F(7) = 37.
  3. Программа для F(10) должна вывести 37; глубина цепочки для F(60) мала, поэтому лимит и прогрев не нужны — достаточно кеша.
from functools import lru_cache @lru_cache(None)def F(n):    if n <= 3:        return 2    if n % 2 == 0:        return F(n - 1) + F(n - 3)    return F(n - 2) + n print(F(10))  # 37 — как при ручной проверкеprint(F(60))  # 1737

Общий алгоритм решения

Мы рассмотрели несколько разных формул и способов вычисления. Теперь соберём их в один алгоритм для задания 16:

Как решать задание 16
  1. Определите область n и базовые значения. Аргумент натуральный, n ≥ 0 или задан отдельно; базовые значения даны в условии — их не нужно вычислять. Проверьте, что база находится там, куда ведёт цепочка (внизу или, как F(n + 4), вверху).
  2. Определите вид зависимости. Одно или несколько предыдущих значений, разные формулы для чётных и нечётных n, шаг не на 1 (//, %), рекурсия вверх или две связанные функции.
  3. Сначала попробуйте упростить. Огромный аргумент и отношение или разность соседних значений — повод раскрыть несколько шагов и сократить. Не сокращается точно — оцените поправку.
  4. Выберите инструмент. Маленький аргумент — таблица вручную; рекурсия с @lru_cache(None) — если есть ветви, два и более вызова, шаг не на 1 или две функции; цикл — для линейной цепочки; лимит рекурсии — если цепочка чуть длиннее 1000; прогрев кеша — при очень длинной цепочке или рекурсии вверх.
  5. Проверьте, что аргумент приближается к базе. F(n) → F(n − 1) → F(n − 2) → … должно дойти до известного значения, а базовые случаи проверяются в программе первыми.
  6. Проверьте границы и малые значения. range(a, b) не включает b. Программа для малых n должна совпасть с ручным счётом.
  7. Подтвердите ответ вторым способом. Кеш — циклом или списком; программа — упрощением; рекурсия вверх — разностью. Если два способа расходятся, ошибка есть в одном из них.

Практика

Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.

Вычислите последовательность

F(1) = 4, F(n) = F(n - 1) + 2n при n > 1. Найдите F(5).

Подсказка

Начните с F(1) и последовательно найдите F(2), F(3), F(4), F(5).

Решение

Вычислим значения снизу вверх.

  1. F(2) = 8
  2. F(3) = 14
  3. F(4) = 22
  4. F(5) = 32

Проследите рекурсивные вызовы

Изучите функцию и заполните вычисления снизу вверх. Какое значение вернёт вызов f(5)?

Рекурсивная функция

def f(n):    if n == 1:        return 1    if n == 2:        return 2    return f(n - 1) + 2 * f(n - 2) # Опорные и вычисляемые значения:# F(1) = 1# F(2) = 2# F(3) = ?# F(4) = ?# F(5) = ?
Подсказка

Сначала найдите F(3), затем F(4). Каждый вызов должен дойти до одного из двух базовых случаев.

Решение

Раскрываем вызовы снизу вверх, не пропуская оба базовых случая.

  1. F(1) = 1 и F(2) = 2 — готовые базовые значения.
  2. F(3) = F(2) + 2F(1) = 2 + 2 · 1 = 4.
  3. F(4) = F(3) + 2F(2) = 4 + 2 · 2 = 8.
  4. F(5) = F(4) + 2F(3) = 8 + 2 · 4 = 16.

Та же рекуррентная формула в Python

def f(n):    if n == 1:        return 1    if n == 2:        return 2    return f(n - 1) + 2 * f(n - 2) print(f(5))  # 16

Используйте два предыдущих значения

F(1) = 1, F(2) = 2, F(n) = 2F(n - 1) + F(n - 2). Найдите F(5).

Подсказка

Храните два последних значения и не пропускайте F(3) и F(4).

Решение

Последовательно применим формулу.

  1. F(3) = 5
  2. F(4) = 12
  3. F(5) = 29

Посчитайте повторяющиеся вызовы

Пусть F(0) = 1, F(1) = 1, а при n > 1 функция возвращает F(n - 1) + F(n - 2). Сколько всего вызовов F произойдёт при вычислении F(6), включая самый первый вызов?

Подсказка

Обозначьте число вызовов через C(n). Для базовых случаев C(0) = C(1) = 1, а для остальных C(n) = 1 + C(n - 1) + C(n - 2).

Решение

Считаем не значения F, а количество входов в функцию. Единица в формуле C(n) учитывает текущий вызов, а два слагаемых — обе рекурсивные ветви.

Последовательно найдём размеры деревьев вызовов.

  1. C(0) = 1 и C(1) = 1.
  2. C(2) = 1 + 1 + 1 = 3.
  3. C(3) = 1 + 3 + 1 = 5, C(4) = 1 + 5 + 3 = 9.
  4. C(5) = 1 + 9 + 5 = 15, C(6) = 1 + 15 + 9 = 25.

Сохранение результатов устраняет повторные вычисления

from functools import cache @cachedef f(n):    if n <= 1:        return 1    return f(n - 1) + f(n - 2)

Сократите отношение

F(1) = 2, F(n) = nF(n - 1). Найдите F(100) / F(98).

Подсказка

Раскройте только F(100) и F(99), не вычисляя всю последовательность.

Решение

Выразим соседние значения через F(98).

  1. F(99) = 99F(98)
  2. F(100) = 100 · 99F(98)
  3. F(100) / F(98) = 9900

Итог

Что получилось

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

Как считать — рекурсией с кешем, циклом, списком, прогревом кеша или алгебраическим сокращением — решает не личный вкус, а то, что именно даёт формула: маленький или огромный аргумент, ветвление, шаг не на 1, одна функция или две, число, количество аргументов или разность соседних значений. И в любом случае ответ проверяют: на малых значениях и вторым способом.

карта выбора способа для задания 16
Сначала упрощаем: огромный аргумент и отношение сокращаем. Затем выбираем инструмент по условию: рекурсия с кешем, цикл, поднятый лимит или прогрев кеша. В любом случае проверяем на малом n и вторым способом.
Проверьте себя
Дано F(1) = 5 и F(n) = F(n − 1) + 3 при n > 1. Можно ли подставить n = 1 в рекуррентную формулу, чтобы найти ещё одно значение?
Нет. Формула работает только при n > 1, а F(1) — отдельно заданный базовый случай. Такая подстановка потребовала бы не определённое в условии значение F(0).
Чему равно F(3) для той же функции?
Сначала F(2) = 5 + 3 = 8, затем F(3) = 8 + 3 = 11. Двигаться нужно от базового случая вверх по одному шагу.
В программе с печатью для F(4) в каком порядке появятся строки «возврат»: от большего n к меньшему или наоборот?
От меньшего к большему: сначала «возврат 2», потом «возврат 3», потом «возврат 4». Вызовы уходят вглубь до базы, а затем результаты возвращаются в обратном порядке.
Функция задана как F(1) = 1, F(2) = 1, F(n) = F(n − 1) + F(n − 2). Что станет главной проблемой прямой рекурсии при F(40): глубина стека или что-то другое?
Не глубина (она около сорока), а огромное количество повторных вычислений: одни и те же значения вызываются заново из разных ветвей дерева вызовов. Здесь нужен кеш, список или две переменные.
Чем @lru_cache(None) отличается от @lru_cache() без аргумента?
None снимает ограничение размера, и кеш запоминает все значения. Без аргумента Python помнит только 128 последних, старые вытесняются и могут вычисляться снова — для длинных цепочек и перебора аргументов это плохо.
Почему два последних значения нельзя бездумно обновлять двумя последовательными присваиваниями?
Первое присваивание перезапишет одно из старых значений, и второе уже сложит не ту пару. Нужно сначала сохранить новое значение или использовать параллельное присваивание Python.
Что вернут 9 / 3 и 9 // 3? Почему это важно, когда аргумент функции должен остаться целым?
9 / 3 даёт 3.0 — дробное число, а 9 // 3 даёт 3 — целое. Для огромных аргументов дробное деление теряет цифры, поэтому аргументы делят через //.
Почему в функции с ветвями по чётности базовый случай проверяют раньше веток?
База — единственное значение, которое задано напрямую. Если её не проверить первой, аргумент может попасть в ветку, которая уведёт цепочку мимо базы (например, n = 1 в ветку нечётных даст F(0)) и вызовет бесконечную рекурсию.
Функция задана как F(n) = F(n + 3) + 1 при n < 5000. В каком порядке прогревать кеш?
От больших n к малым, начиная примерно с базы (около 5000): F(n) зависит от F(n + 3), поэтому это значение должно быть уже сохранено. Порядок выбирают против направления зависимости.
Нужно посчитать n от 1 до 300 включительно. Какую строку цикла написать?
for n in range(1, 301): — правая граница range не входит, поэтому берётся «последнее нужное значение + 1».
Если F(n) = n·F(n − 1), нужно ли вычислять всю последовательность от F(1), чтобы найти F(2024) / F(2022)?
Нет. Достаточно раскрыть два последних шага: F(2024) = 2024·2023·F(2022), после чего F(2022) сокращается.
Выберите способ вычисления для каждого условия: (а) F(n) = 3·F(n − 1) + 2, нужно F(50); (б) значение зависит от F(n // 2) и чётности n; (в) нужна разность F(3000) − F(2997) для F(n) = F(n − 1) + n.
(а) Линейная цепочка на 50 шагов — цикл или рекурсия с кешем. (б) Ветвление и шаг не на 1 — рекурсия с @lru_cache(None). (в) Разность из трёх шагов — сумма 3000 + 2999 + 2998 без программы; программой подтверждают ответ.