I wanted to basically try calling an index of the list and if it doesn't exist, try generating it from the previous two indices. However if they don't exist, then keep going back until two existing cached results are found and work off of those. I wanted to guard against errors from exceeding the recursion depth without necessarily rejecting a number. For instance, calling
fib(1800) immediately exceeds (my) recursion depth, but my
while loop will allow you to get the result.
For values that prove too high, I reject them with a
ValueError. Though this does print every line of the recursive call's error. I'd like to know how I can handle this
raise better to avoid that.
I'd also like to know if I could actually increase the viable number, if there's a good way to calculate what is a reasonable number better. I currently halve the recursion limit value mostly for safety but I'm sure that's not the best way. I'm also interested to know about any potential dangers of the cache getting too large and how those should be dealt with.
from sys import getrecursionlimit rec = getrecursionlimit() * 0.9 def fib(n, rec=rec, memo=[0,1]): """Return the sum of the fibonacci sequence up until n rec is the recursion limit, and should be left as default. memo is the cached list of fibonacci values. raises a ValueError if your value is too high. If that happens, call lower values to build up the cache first.""" while (n - len(memo)) >= rec: rec /= 2 try: fib(int(len(memo) + rec), rec) except RuntimeError: raise ValueError("Input is too high to calculate.") try: return memo[n] except IndexError: # Calculate the answer since it's not stored memo.append(fib(n - 1) + fib(n - 2)) return memo[n]