← Все вопросы
Задание 16 КЕГЭ: рекурсивная функция F(n) считается долго и неверно — что проверить?
7
Задание 16 с рекурсией: дано F(n) = F(n-1) + F(n-2) + n (с базой), надо найти F(какого-то большого n). Пишу рекурсию на питоне, но для больших n считается медленно или падает с RecursionError. Как правильно посчитать?
2 ответа
13
✓ Принятый ответ — помог автору
Голая рекурсия пересчитывает одно и то же миллионы раз — поэтому медленно. Лекарство — кэширование через lru_cache:
from functools import lru_cache
import sys
sys.setrecursionlimit(100000) # на случай глубокой рекурсии
@lru_cache(None)
def F(n):
if n <= 1: # база — переписывай ТОЧНО как в задании
return 1
return F(n - 1) + F(n - 2) + n
print(F(2026))
Две частые причины неверного ответа:
- База перенесена неточно — самая частая ошибка. Перепиши условие останова буква в букву из задания (
if n == 1: return ...,if n == 2: return ...). - Забыл
lru_cache— тогда либо вечность, либо стек переполнен.
С @lru_cache(None) каждое F(n) считается один раз, и даже большие n считаются мгновенно.
5
Если боишься RecursionError даже с увеличенным лимитом — перепиши в цикл снизу вверх (табуляция):
F = [0] * (n + 1)
F[1] = 1
F[2] = ... # по базе
for i in range(3, n + 1):
F[i] = F[i-1] + F[i-2] + i
print(F[n])
Тот же результат, но без рекурсии вообще — стек не переполнится при любом n. Главное — ровно те же базовые значения, что в условии.
Ваш ответ
Войдите, чтобы ответить на вопрос.