I'm a student, our teacher asked us to do the task below(I translated it into English for convenience)
The algorithm for computing the function F(n), where n is a natural number, is given by the following relations:
F(n) = n if n ≥ 10,000,
F(n) = n/4 + F(n / 4 + 2) if n < 10 000 and n is divisible by 4,
F(n) = 1 + F(n + 2) , if n < 10 000 and n is not divisible by 4.
What is the value of the expression F(174) - F(3)?
Correct Answer: 67
He recommended us to use lru_cache for caching and faster recursion, but this caching doesn't work on desktop pc, only on online Python interpreters
My code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
@lru_cache(None)
def F(n):
if n >= 10000:
return n
elif n % 4 == 0:
return n // 4 + F(n // 4 + 2)
else:
return 1 + F(n + 2)
print(F(174) - F(3))
VScode: The program is running in VScode, the output response is empty https://i.imgur.com/jZwLZyb.png
OnlineGDB: The program is run in OnlineGDB, the correct answer is displayed
If I comment out the lines with cache, everything will work without it. The trouble is that we have already solved similar tasks, and there was the same situation - you can't do without caching, but it works only in online interpreters
The funniest thing is that these tasks are intended for an exam, where access to an online interpreter, of course, will not be available.
The program should output a 67 answer both on the PC and in online interpreters, but it only happens in the last case. Maybe it doesn't make sense to use caching in this task, but I can't understand why it refuses to work
Your code segfaulted.
sys.setrecursionlimit(10**6) doesn't mean you can actually recurse a million levels deep. It means Python's safety checks won't stop you from trying. Blow past the limit of your C stack, and you'll crash.
Different systems have different default stack sizes. You might be able to go deep enough for your code to succeed on the online interpreters you tried, but on your PC, you didn't have enough stack space.
