How to Make Python remember a list created inside a function for future use

Question

Below is an iterative calculation of Fibonacci Sequence.

def fibonacci(n):
    if n < 0:
            raise ValueError("invalid index!")
    if n==0:
            return 0
    if n==1:
            return 1

    f = [0,1]
    for i in range(2,n+1):
            f.append(f[i-1] + f[i-2])
    return f[n]

Code Source: brilliant.org

As it is, the list f is a local variable inside the function and will be recreated and repopulated each time the fibonacci function is called. How could this code snippet be rewritten so that Python would not need to recalculate fibonacci(5) once it was called and could use it the next time fibonacci(5) or above was called? I know global variable is one option but what would be the most "Pythonic" way of doing this?

Answer 1

You can store the f in a variable outside the scope of the function. For instance:

def memoize_fibonacci():
    f = [0,1]
    def inner_fibonacci(n):
        if n < 0:
                raise ValueError("invalid index!")
        for i in range(len(f),n+1):
                f.append(f[i-1] + f[i-2])
        return f[n]
    return inner_fibonacci

So each time we inspect the length of f. In case we have not generated the requested index yet, we generate until we obtain the index. Regardless whether we extend the list, we eventually can return f[n].

Now we can extract the fibonacci function, with:

fibonacci = memoize_fibonacci()

If we now query twice for the 200'000th element, the second time it is faster.