I decided to write a function that would generate an index of the Fibonacci sequence making use of Python's mutable default parameter. It's inspired by a question I answered on Stack Overflow where someone was converting a script with this idea from JavaScript to Python and I wanted to expand on it to see how I could handle it.

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]
  • 3
    Computing a Fibonacci number in this way doesn't make any sense! A simple 'for' loop is all you need. – Chris Aug 20 '15 at 19:02
up vote 3 down vote accepted

As pointed out, top-down recursive approaches are almost never a good idea when it comes to Fibonacci numbers. Consider the alternative iterative approach:

def fib(n):
    while n <= len(fib.cache):
        fib.cache.append(fib.cache[-1] + fib.cache[-2])
    return fib.cache[n]
fib.cache = [0, 1]

Notice how the memoization cache is stored as an attribute of the function, which is the closest thing in Python to having a static variable inside a function.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.