SuperFib - an example of using lexical closure in Python

This story begins with simple implementation of a function that calculates Fibonacci numbers.

def fib(n):
    return 1 if n == 1 or n == 2 else fib(n-1) + fib(n-2)

Assuming that we are using 1-based indices, we can run a couple of tests and see that it works. Of course, fib(35) takes some time to calculate - about 15 seconds on my laptop.

Now, if you don't know what lexical closure is, I recommend reading about it on Wikipedia) before going further. Let's try to cache the results, but also be better than using conventional memoization - not only will we cache the final result of each call, but also intermediate results.

def fib():
    _dict = dict()
    def inner(n):
        nonlocal _dict
        if n == 1 or n == 2:
            return 1
        else:
            try:
                return _dict[n]
            except KeyError:
                _dict[n] = inner(n-1) + inner(n-2)
                return _dict[n]
    return inner

f = fib()
f(1000) returns instantly, with:
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

However, if I call f(1500) without calling f(1000) first, the calculation will not finish and my interpreter will crash or at least restart because of stack evaluation overflow.

But if I ran f(1000) and then f(1500) and then f(2000) and so on and so forth, advancing by 500 each time, I can very quickly get to quite far elements of Fibonacci sequence. Calculating 10 000th element is quick and easy, compared to conventional approach. We can quickly get to the point where printing the numbers to the console takes more time than actually calculating them.