Установка ограничения рекурсии не работает в автономном интерпретаторе Python, но работает в онлайн-интерпретаторах
Питон 3.12.5
The algorithm for calculating the value of the function F(n), where n is a natural number, is given
by the following ratios:
F(n) = 1 for n = 1;
F(n) = 2 for n = 2;
F(n) = n * (n - 1) + F(n - 1) + F(n - 2) if n > 2.
What is the value of the expression F(2024) - F(2022) - 2 * F(2021) - F(2020)?
Сначала я просто использовал рекурсию с большим лимитом, но обнаружил, что программа работает СЛИШКОМ медленно (потому что я не использовал @lru_cache), посмотрел видео с решением этой задачи и использовал этот код
from functools import lru_cache
import sys
sys.setrecursionlimit(50000000)
@lru_cache
def F(n):
if n == 1:
return 1
if n == 2:
return 2
return n*(n-1) + F(n-1) + F(n-2)
print(F(2024) - F(2022) - 2*F(2021) - F(2020))
Автору видео это помогло. Когда я попробовал это в онлайн-переводчике, это тоже сработало, и я получил правильный ответ. Но на моем ПК это не работает. Я получаю RecursionError, хотя установил предел рекурсии на 50000000:
return n*(n-1) + F(n-1) + F(n-2)
^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
Что мне делать? Может быть, есть какие-то другие решения?
@ThierryLathuille Хорошо, благодаря этому методу я получил правильный ответ (12271520). Я просто решил решить все задачи не зная основы поэтому выбрал не лучший метод. Но в любом случае это не решает ошибки рекурсии
@ThierryLathuille в любом случае, спасибо
Ответы 1
Кажется, вы столкнулись с той же ошибкой, о которой сообщалось в выпуске № 112215 — 3.12 setrecursionlimit игнорируется в связи с @functools.cache . См. также #112282. Похоже, что серьезная регрессия была введена в версии 3.12 и все еще присутствует в версии 3.12.5.
Для реальной задачи, которую вы пытаетесь решить, вам вообще не нужна функция, вычисляющая числа типа Фибоначчи. Вы можете получить ответ, расширяя рекурсивные 𝐹-члены большими аргументами, пока у нас не останется выражение, которое содержит только несколько 𝐹2021 и 𝐹2020, которые отменяют друг друга:
Начнем с:
𝐹2024 − 𝐹2022 − 2𝐹2021 − 𝐹2020
Мы можем расширить это 𝐹2024:
2024⋅2023 + 𝐹2023 + 𝐹2022 − 𝐹2022 − 2𝐹2021 − 𝐹2020
Мы можем исключить 𝐹2022 − 𝐹2022:
2024⋅2023 + 𝐹2023 − 2𝐹2021 − 𝐹2020
Мы можем расширить это 𝐹2023:
2024⋅2023 + 2023⋅2022 + 𝐹2022 + 𝐹2021 − 2𝐹2021 − 𝐹2020
Мы можем уменьшить 𝐹2021 − 2𝐹2021 до − 𝐹2021:
2024⋅2023 + 2023⋅2022 + 𝐹2022 − 𝐹2021 − 𝐹2020
Мы можем расширить это 𝐹2022:
2024⋅2023 + 2023⋅2022 + 2022⋅2021 + 𝐹2021 + 𝐹2020 − 𝐹2021 − 𝐹2020
Теперь мы можем исключить все члены 𝐹, и результат будет следующим:
2024⋅2023 + 2023⋅2022 + 2022⋅2021 = 12271520
0 – неправильный ответ. Также вызов setrecursionlimit() с 50000000 не представляет проблем. Python возвращает ошибку, только если я передаю значение больше 10**10
12271520, кстати, правильный ответ.
Возможно я ошибаюсь в терминах, поэтому скажем так, лимит в 3000 проблему не решает. Я все еще получаю ту же ошибку
Возможно, я был слишком минималистичным, предложив 3000. Установите значение 6000, и все должно работать. Вы не должны получить трассировку стека с упоминанием 996 рекурсивных вызовов, если вы установите глубину рекурсии на 6000. У меня это работает в разных средах.
Извините, я пропустил, что F не является F стандартного числа Фибоначчи, но имеет дополнительный член в формуле рекурсии. Я переписал свой ответ, чтобы принять это во внимание.
«У меня работает в разных средах» — С какими версиями Python? (Не уверен, когда именно они внесли соответствующие изменения, думаю, это была версия 3.12 или 3.11)
Хорошая мысль, @nocomment. Я только что попробовал еще раз на 3.12.5, и проблема повторилась. Оказывается, это зарегистрированная ошибка.
Да, вот и все. Кстати, вы можете «исправить» это, избегая реализации functools на C, тогда ограничение, установленное sys.setrecursionlimit, действительно применяется. Но это хак.
Нет необходимости запускать код, чтобы найти ответ. Просто используйте определение функции: упрощение выражения и получение простого числового результата займут две минуты. Выбор значений, вероятно, был сделан для того, чтобы люди, пытающиеся его перебрать, столкнулись с ошибками рекурсии.