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():

def inner(n):

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

43466557686937456435688527675…

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:43466557686937456435688527675…