Задание 16
тема 2 из 2

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

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

Основа для заданий19202123Главная тема в задании16На карте навыков

Как вычислить рекурсивную функцию

Функция задана базовым случаем, например F(1)=1F(1) = 1, и рекурсивным переходом, например F(n)=n⋅F(n−1)F(n) = n \cdot F(n - 1). Условия проверяют сверху вниз.

  • Небольшой аргумент: заполните таблицу значений от базового случая вверх до нужного nn.
  • Программа: функция def F(n) повторяет определение, каждое условие — отдельный if с return.
  • Глубина больше 1000 вызовов: добавьте sys.setrecursionlimit(10000). Два вызова в переходе: добавьте @lru_cache(None).
  • Частное или разность значений: разверните переход на несколько шагов, общий множитель или общее слагаемое сократится.
  • Делите целые числа только через //.

Базовый случай, переход и стек вызовов

Рекурсивная функция — функция, которая вызывает саму себя. Её задают двумя частями. Базовый случай — аргументы, при которых значение дано сразу: F(1)=1F(1) = 1. Рекурсивный переход — формула, которая выражает F(n)F(n) через значения функции от других аргументов: F(n)=n⋅F(n−1)F(n) = n \cdot F(n - 1) при n>1n > 1. Каждый вызов должен приближать аргумент к базовому случаю, иначе вычисление не закончится.

Незаконченные вызовы компьютер хранит в стеке вызовов. Вызов F(5)F(5) ждёт значения F(4)F(4), тот ждёт F(3)F(3), и так до базового случая. Затем значения возвращаются в обратном порядке: последний начатый вызов заканчивается первым. Число вызовов, которые одновременно лежат в стеке, называют глубиной рекурсии.

Пример

Функция задана так: F(1)=1F(1) = 1; F(n)=n⋅F(n−1)F(n) = n \cdot F(n - 1) при n>1n > 1. Найдите F(5)F(5) и глубину рекурсии.

  1. 1.Спуск: F(5)F(5) вызывает F(4)F(4), затем F(3)F(3), F(2)F(2) и F(1)F(1). В стеке пять вызовов, глубина 5.
  2. 2.F(1)=1F(1) = 1 — базовый случай, спуск закончен.
  3. 3.Возврат: F(2)=2⋅1=2F(2) = 2 \cdot 1 = 2, F(3)=3⋅2=6F(3) = 3 \cdot 2 = 6, F(4)=4⋅6=24F(4) = 4 \cdot 6 = 24, F(5)=5⋅24=120F(5) = 5 \cdot 24 = 120.

Ответ: F(5)=120F(5) = 120, глубина 5

Вычисление по таблице снизу вверх

Чтобы найти значение без компьютера, не спускайтесь от nn вниз, а идите от базового случая вверх. Запишите F(1)F(1), F(2)F(2), F(3)F(3) и так далее. Для каждого аргумента выберите формулу по условию: чётный ли nn, больше ли он границы. Подставьте значения, которые уже стоят в таблице.

Если переход для нечётных nn ссылается на F(n−2)F(n - 2), а для чётных — на F(n−1)F(n - 1), таблицу всё равно заполняют подряд: каждое значение нужно для следующих.

Пример

F(1)=1F(1) = 1; F(n)=n+F(n−1)F(n) = n + F(n - 1), если nn чётно; F(n)=3⋅F(n−2)F(n) = 3 \cdot F(n - 2), если n>1n > 1 и nn нечётно. Найдите F(7)F(7).

  1. 1.F(1)=1F(1) = 1 — базовый случай.
  2. 2.F(2)=2+F(1)=3F(2) = 2 + F(1) = 3, F(3)=3⋅F(1)=3F(3) = 3 \cdot F(1) = 3.
  3. 3.F(4)=4+F(3)=7F(4) = 4 + F(3) = 7, F(5)=3⋅F(3)=9F(5) = 3 \cdot F(3) = 9.
  4. 4.F(6)=6+F(5)=15F(6) = 6 + F(5) = 15, F(7)=3⋅F(5)=27F(7) = 3 \cdot F(5) = 27.

Ответ: 2727

Программа повторяет определение

В Python функцию пишут через def. Каждое условие определения — отдельный if с return, в том же порядке, что в условии. Базовый случай проверяют первым: иначе при малом nn сработает переход, и вызовы не остановятся. «nn чётно» записывают как n % 2 == 0. Последнему случаю if не нужен: до него доходят, только если остальные условия ложны.

Если переход содержит сумму ∑i=1n−1F(i)\sum_{i=1}^{n-1} F(i), в return пишут sum(F(i) for i in range(1, n)). Основы функций и циклов — в теме Python для ЕГЭ.

Пример

F(n)=1F(n) = 1 при n≤2n \le 2; F(n)=2+F(n−1)F(n) = 2 + F(n - 1), если n>2n > 2 и nn чётно; F(n)=n+F(n−2)F(n) = n + F(n - 2), если n>2n > 2 и nn нечётно. Найдите F(30)F(30).

  1. 1.Первый if — базовый случай n <= 2.
  2. 2.Второй if проверяет чётность и возвращает 2 + F(n - 1).
  3. 3.Остался случай нечётного n>2n > 2: return n + F(n - 2).
  4. 4.Глубина рекурсии около 30, запас не нужен. Программа печатает 227.

Ответ: 227227

Целочисленное деление больших значений

Значения рекурсивных функций в ЕГЭ — огромные целые числа: F(2030)F(2030) из примера выше содержит больше 5800 цифр. Python хранит их точно. Но знак / всегда даёт дробное число float, а у него только около 16 верных цифр. Частное / печатается с .0 или в виде 1.16e+33 и теряет последние цифры.

Если в вопросе частное значений, а ответ — целое число, делите через //. Этот знак отбрасывает остаток и сохраняет все цифры.

Пример

F(1)=1F(1) = 1; F(n)=n⋅F(n−1)F(n) = n \cdot F(n - 1) при n>1n > 1. Найдите F(2030)/F(2020)F(2030) / F(2020).

  1. 1.Глубина рекурсии больше 2000, поэтому программа поднимает предел: глубина рекурсии.
  2. 2.Строка с / печатает 1.162299654171746e+33: это приближение, в нём 16 цифр из 34.
  3. 3.Строка с // печатает точное значение.

Ответ: 11622996541717460391521287177920001162299654171746039152128717792000

Глубина рекурсии

Python ограничивает глубину рекурсии: по умолчанию в стеке не больше 1000 вызовов. Для F(2100)F(2100) с переходом F(n)=n⋅F(n−1)F(n) = n \cdot F(n - 1) нужно 2100 вызовов, и программа останавливается с ошибкой RecursionError. Предел поднимают в начале программы: import sys и sys.setrecursionlimit(10000). Новый предел берут с запасом, больше самого глубокого аргумента.

Пример

F(1)=1F(1) = 1; F(n)=n⋅F(n−1)F(n) = n \cdot F(n - 1) при n>1n > 1. Найдите (F(2100)−3⋅F(2099))/F(2098)(F(2100) - 3 \cdot F(2099)) / F(2098).

  1. 1.Глубина вызова F(2100)F(2100) — 2100, это больше 1000. Поднимаем предел до 10000.
  2. 2.Функция повторяет определение, частное берём через //.
  3. 3.Программа печатает 4401603.

Ответ: 44016034401603

Мемоизация

Если переход вызывает функцию дважды, например F(n)=F(n−1)+F(n−2)F(n) = F(n - 1) + F(n - 2), одни и те же значения считаются много раз. Число вызовов растёт как сами значения: для F(40)F(40) без памяти нужно больше 200 миллионов вызовов. Мемоизация — запоминание уже найденных значений: каждое F(k)F(k) считается один раз, следующий вызов берёт готовый ответ. В Python её даёт строка @lru_cache(None) перед def и from functools import lru_cache в начале программы.

Мемоизация помогает и с глубиной. Если вызвать функцию по порядку, for i in range(1, n + 1): F(i), каждый вызов находит в памяти предыдущее значение и уходит вглубь только на один шаг. Тогда предел глубины поднимать не нужно.

Пример

F(n)=1F(n) = 1 при n≤2n \le 2; F(n)=F(n−1)+F(n−2)F(n) = F(n - 1) + F(n - 2) при n>2n > 2. Найдите F(100)F(100).

  1. 1.Без памяти программа сделала бы больше 102010^{20} вызовов и не закончила бы работу.
  2. 2.С @lru_cache(None) каждое из значений F(1)F(1), …, F(100)F(100) считается один раз.
  3. 3.Программа печатает ответ сразу.

Ответ: 354224848179261915075354224848179261915075

Разность значений: разверните переход

Если спрашивают разность значений с близкими аргументами, вычислять сами значения не нужно. Подставьте переход в себя несколько раз: F(n)=g(n)+F(n−1)=g(n)+g(n−1)+F(n−2)F(n) = g(n) + F(n - 1) = g(n) + g(n - 1) + F(n - 2). Тогда F(n)−F(n−k)F(n) - F(n - k) — сумма kk слагаемых gg. Если в переходе есть множитель, например F(n)=3n+2⋅F(n−1)F(n) = 3n + 2 \cdot F(n - 1), развёртка даёт F(n)=3n+6(n−1)+4⋅F(n−2)F(n) = 3n + 6(n - 1) + 4 \cdot F(n - 2), и выражение F(n)−4⋅F(n−2)F(n) - 4 \cdot F(n - 2) не содержит неизвестных значений.

Проверить ответ можно программой. Чтобы не поднимать предел глубины, вызовите функцию с мемоизацией по порядку: мемоизация.

Пример

F(1)=2F(1) = 2; F(n)=3n+F(n−1)F(n) = 3n + F(n - 1) при n>1n > 1. Найдите F(2030)−F(2027)F(2030) - F(2027).

  1. 1.Разворачиваем три шага: F(2030)=3⋅2030+3⋅2029+3⋅2028+F(2027)F(2030) = 3 \cdot 2030 + 3 \cdot 2029 + 3 \cdot 2028 + F(2027).
  2. 2.F(2030)−F(2027)=3⋅(2030+2029+2028)=3⋅6087=18261F(2030) - F(2027) = 3 \cdot (2030 + 2029 + 2028) = 3 \cdot 6087 = 18261.
  3. 3.Программа вызывает F(1)F(1), …, F(2030)F(2030) по порядку и печатает то же число.

Ответ: 1826118261

Частное значений: сократите общий множитель

Если переход умножает, F(n)=n⋅F(n−1)F(n) = n \cdot F(n - 1), разверните его до общего множителя: F(n)=n⋅(n−1)⋅F(n−2)F(n) = n \cdot (n - 1) \cdot F(n - 2). Отсюда F(n)F(n−k)=n⋅(n−1)⋅…⋅(n−k+1)\dfrac{F(n)}{F(n - k)} = n \cdot (n - 1) \cdot \ldots \cdot (n - k + 1): произведение kk множителей. Если в числителе сумма или разность значений, выразите каждое значение через младшее F(n−k)F(n - k), вынесите его за скобки и сократите.

Пример задания

Открытый банк ФИПИ

Алгоритм вычисления значения функции 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+1)F(n) = n \cdot F(n + 1) при n≤2024n \le 2024, а базовый случай стоит сверху: F(n)=nF(n) = n при n>2024n > 2024. Вызовы идут вверх, пока аргумент не перейдёт границу. Все правила те же: разверните переход от меньшего аргумента к большему, и общий множитель сократится. В программе меняется только условие базового случая.

Пример задания

Открытый банк ФИПИ

Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n при n > 2024;
F(n) = n × F(n + 1), если n ≤ 2024.
Чему равно значение выражения F(2022) / F(2024)?

Потренируйте навык

Все задания на этот навык

Решать