Задание 16: рекурсивные функции на Python
Коротко
Функция задаётся через свои значения при меньших аргументах: например, F(n) = n при n < 3, F(n) = F(n − 1) + 2·F(n − 2) при n ≥ 3. Значение считают программой. Для больших n нужен кэш (functools.lru_cache), иначе вычисления повторяются экспоненциально, и увеличенный предел рекурсии sys.setrecursionlimit. Можно считать и снизу вверх в цикле.
Шаблон
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)
@lru_cache(None)
def F(n):
if n < 3:
return n
return F(n - 1) + 2 * F(n - 2)
print(F(10))
Большие аргументы
Если нужно F(2026), вызывайте F для возрастающих n по порядку (цикл), чтобы кэш заполнялся без глубокой рекурсии.
Типичные ошибки
- Нет кэша — программа считает очень долго.
- Неверно перенесено базовое условие (n < 3 против n ≤ 3).
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 16
Пример 1 из 2
F(n) = n при n < 3; F(n) = F(n − 1) + 2·F(n − 2). Найдите F(10).
- Разбор
- F(1) = 1, F(2) = 2, F(3) = 4, F(4) = 8 … каждое следующее удваивается; программа даёт 512.
- Ответ
- 512
Пример 2 из 2
Зачем lru_cache?
- Разбор
- Он запоминает уже вычисленные значения, и каждое F(n) считается один раз.
- Ответ
- Чтобы не пересчитывать значения
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Что делает lru_cache?
Показать ответ
Ответ: Запоминает результаты функции.
Мемоизация.
- Вопрос 2 из 5
Зачем setrecursionlimit?
Показать ответ
Ответ: Увеличить допустимую глубину рекурсии.
По умолчанию около 1000.
- Вопрос 3 из 5
Что такое базовый случай?
Показать ответ
Ответ: Значение без рекурсивного вызова.
Например, n < 3.
- Вопрос 4 из 5
Можно ли решать циклом?
Показать ответ
Ответ: Да.
Снизу вверх.
- Вопрос 5 из 5
Что будет без базового случая?
Показать ответ
Ответ: Бесконечная рекурсия.
Ошибка RecursionError.
Проверьте всё задание 16, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти