Рекурсивные функции
Рекурсивная функция задаёт своё значение через значения той же функции от меньших аргументов и через базовый случай. Небольшое значение считают по таблице снизу вверх или программой, которая повторяет определение. Для больших аргументов программе нужны запас глубины рекурсии и мемоизация, а частное или разность значений часто проще найти, если развернуть формулу.
Как вычислить рекурсивную функцию
Функция задана базовым случаем, например , и рекурсивным переходом, например . Условия проверяют сверху вниз.
- Небольшой аргумент: заполните таблицу значений от базового случая вверх до нужного .
- Программа: функция
def F(n)повторяет определение, каждое условие — отдельныйifсreturn. - Глубина больше 1000 вызовов: добавьте
sys.setrecursionlimit(10000). Два вызова в переходе: добавьте@lru_cache(None). - Частное или разность значений: разверните переход на несколько шагов, общий множитель или общее слагаемое сократится.
- Делите целые числа только через
//.
Базовый случай, переход и стек вызовов
Рекурсивная функция — функция, которая вызывает саму себя. Её задают двумя частями. Базовый случай — аргументы, при которых значение дано сразу: . Рекурсивный переход — формула, которая выражает через значения функции от других аргументов: при . Каждый вызов должен приближать аргумент к базовому случаю, иначе вычисление не закончится.
Незаконченные вызовы компьютер хранит в стеке вызовов. Вызов ждёт значения , тот ждёт , и так до базового случая. Затем значения возвращаются в обратном порядке: последний начатый вызов заканчивается первым. Число вызовов, которые одновременно лежат в стеке, называют глубиной рекурсии.
Пример
Функция задана так: ; при . Найдите и глубину рекурсии.
- 1.Спуск: вызывает , затем , и . В стеке пять вызовов, глубина 5.
- 2. — базовый случай, спуск закончен.
- 3.Возврат: , , , .
Ответ: , глубина 5
Вычисление по таблице снизу вверх
Чтобы найти значение без компьютера, не спускайтесь от вниз, а идите от базового случая вверх. Запишите , , и так далее. Для каждого аргумента выберите формулу по условию: чётный ли , больше ли он границы. Подставьте значения, которые уже стоят в таблице.
Если переход для нечётных ссылается на , а для чётных — на , таблицу всё равно заполняют подряд: каждое значение нужно для следующих.
Пример
; , если чётно; , если и нечётно. Найдите .
- 1. — базовый случай.
- 2., .
- 3., .
- 4., .
Ответ:
Программа повторяет определение
В Python функцию пишут через def. Каждое условие определения — отдельный if с return, в том же порядке, что в условии. Базовый случай проверяют первым: иначе при малом сработает переход, и вызовы не остановятся. « чётно» записывают как n % 2 == 0. Последнему случаю if не нужен: до него доходят, только если остальные условия ложны.
Если переход содержит сумму , в return пишут sum(F(i) for i in range(1, n)). Основы функций и циклов — в теме Python для ЕГЭ.
Пример
при ; , если и чётно; , если и нечётно. Найдите .
- 1.Первый
if— базовый случайn <= 2. - 2.Второй
ifпроверяет чётность и возвращает2 + F(n - 1). - 3.Остался случай нечётного :
return n + F(n - 2). - 4.Глубина рекурсии около 30, запас не нужен. Программа печатает 227.
Ответ:
Целочисленное деление больших значений
Значения рекурсивных функций в ЕГЭ — огромные целые числа: из примера выше содержит больше 5800 цифр. Python хранит их точно. Но знак / всегда даёт дробное число float, а у него только около 16 верных цифр. Частное / печатается с .0 или в виде 1.16e+33 и теряет последние цифры.
Если в вопросе частное значений, а ответ — целое число, делите через //. Этот знак отбрасывает остаток и сохраняет все цифры.
Пример
; при . Найдите .
- 1.Глубина рекурсии больше 2000, поэтому программа поднимает предел: глубина рекурсии.
- 2.Строка с
/печатает1.162299654171746e+33: это приближение, в нём 16 цифр из 34. - 3.Строка с
//печатает точное значение.
Ответ:
Глубина рекурсии
Python ограничивает глубину рекурсии: по умолчанию в стеке не больше 1000 вызовов. Для с переходом нужно 2100 вызовов, и программа останавливается с ошибкой RecursionError. Предел поднимают в начале программы: import sys и sys.setrecursionlimit(10000). Новый предел берут с запасом, больше самого глубокого аргумента.
Пример
; при . Найдите .
- 1.Глубина вызова — 2100, это больше 1000. Поднимаем предел до 10000.
- 2.Функция повторяет определение, частное берём через
//. - 3.Программа печатает 4401603.
Ответ:
Мемоизация
Если переход вызывает функцию дважды, например , одни и те же значения считаются много раз. Число вызовов растёт как сами значения: для без памяти нужно больше 200 миллионов вызовов. Мемоизация — запоминание уже найденных значений: каждое считается один раз, следующий вызов берёт готовый ответ. В Python её даёт строка @lru_cache(None) перед def и from functools import lru_cache в начале программы.
Мемоизация помогает и с глубиной. Если вызвать функцию по порядку, for i in range(1, n + 1): F(i), каждый вызов находит в памяти предыдущее значение и уходит вглубь только на один шаг. Тогда предел глубины поднимать не нужно.
Пример
при ; при . Найдите .
- 1.Без памяти программа сделала бы больше вызовов и не закончила бы работу.
- 2.С
@lru_cache(None)каждое из значений , …, считается один раз. - 3.Программа печатает ответ сразу.
Ответ:
Разность значений: разверните переход
Если спрашивают разность значений с близкими аргументами, вычислять сами значения не нужно. Подставьте переход в себя несколько раз: . Тогда — сумма слагаемых . Если в переходе есть множитель, например , развёртка даёт , и выражение не содержит неизвестных значений.
Проверить ответ можно программой. Чтобы не поднимать предел глубины, вызовите функцию с мемоизацией по порядку: мемоизация.
Пример
; при . Найдите .
- 1.Разворачиваем три шага: .
- 2..
- 3.Программа вызывает , …, по порядку и печатает то же число.
Ответ:
Частное значений: сократите общий множитель
Если переход умножает, , разверните его до общего множителя: . Отсюда : произведение множителей. Если в числителе сумма или разность значений, выразите каждое значение через младшее , вынесите его за скобки и сократите.
Пример задания
Открытый банк ФИПИ
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения (F(2024) − F(2023)) / F(2022)?
Рекурсия с ростом аргумента
Иногда переход ссылается на больший аргумент: при , а базовый случай стоит сверху: при . Вызовы идут вверх, пока аргумент не перейдёт границу. Все правила те же: разверните переход от меньшего аргумента к большему, и общий множитель сократится. В программе меняется только условие базового случая.
Пример задания
Открытый банк ФИПИ
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n при n > 2024;
F(n) = n × F(n + 1), если n ≤ 2024.
Чему равно значение выражения F(2022) / F(2024)?