1

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)?

At first I just used recursion with the big limit, but I found out that the program runs TOOOOOOO slow (because I didn't use @lru_cache), I watched a video with the solution of this task and used this code

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))

It worked for the author of the video. When I had tried it in an online interpretator, it worked too and I got the correct answer. But it doesn't work on my PC. I get RecursionError although I set the recursion limit to 50000000:

return n*(n-1) + F(n-1) + F(n-2)
                     ^^^^^^
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

What do I do? Maybe there are some other solutions?

Improve this question
3
  • 1
    There's no need to run the code to find the answer. Just use the definition of the function, it's a two minutes work to simplify the expression and get the simple numerical result. The choice of values was probably made so that people trying to bruteforce it would encounter recursion errors. Commented Sep 4, 2024 at 10:26
  • @ThierryLathuille Well, I got the correct answer (12271520) thanks to this method. I just decided to solve all tasks without knowing the basis so I chose not the best method. But anyway it doesn't solve recursion errors Commented Sep 4, 2024 at 11:54
  • @ThierryLathuille anyway, thanks you Commented Sep 4, 2024 at 12:04

1 Answer 1

Reset to default
4

It seems you have bumped into the same bug as reported in issue #112215 - 3.12 setrecursionlimit is ignored in connection with @functools.cache. See also #112282. It looks like a major regression was introduced in 3.12 and is still present in 3.12.5.

For the actual challenge you try to solve, you don't need a function that calculates Fibonacci-like numbers at all. You can derive the answer by expanding the recursive 𝐹-terms with greater arguments until we're left with an expression that just has a number of 𝐹2021 and 𝐹2020, which happen to cancel each other:

We start with:

      𝐹2024 − 𝐹2022 − 2𝐹2021 − 𝐹2020

We can expand that 𝐹2024:

      2024⋅2023 + 𝐹2023 + 𝐹2022 − 𝐹2022 − 2𝐹2021 − 𝐹2020

We can eliminate 𝐹2022 − 𝐹2022:

      2024⋅2023 + 𝐹2023 − 2𝐹2021 − 𝐹2020

We can expand that 𝐹2023:

      2024⋅2023 + 2023⋅2022 + 𝐹2022 + 𝐹2021 − 2𝐹2021 − 𝐹2020

We can reduce 𝐹2021 − 2𝐹2021, to − 𝐹2021:

      2024⋅2023 + 2023⋅2022 + 𝐹2022 − 𝐹2021 − 𝐹2020

We can expand that 𝐹2022:

      2024⋅2023 + 2023⋅2022 + 2022⋅2021 + 𝐹2021 + 𝐹2020 − 𝐹2021 − 𝐹2020

We can now eliminate all 𝐹 terms, and so the result is:

      2024⋅2023 + 2023⋅2022 + 2022⋅2021 = 12271520

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

0 is a wrong answer. Also calling setrecursionlimit() with 50000000 is not problematic. Python returns error only if I transmit the value more than 10**10
12271520 is the correct answer btw
I may be mistaken in terms, so let's just say that the 3000 limit does not solve the problem. I still get the same error
I might I have been to minimalistic with suggesting 3000. Set it to 6000, and it should work. You shouldn't get a stack trace with a mention of 996 recursive calls when you set the recursion depth to 6000. That works for me on different environments.
Sorry, I missed that F is not the F of standard Fibonacci, but has an extra term in the recurrence formula. I rewrote my answer to take that into account.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.