Lesson 12.8
Fibonacci numbers are defined by recursion: each one is the sum of the two before it.
def fib(n, memo={}):
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
fib(50) that already takes very long;memo is a dictionary of results: first check whether it has been worked out already;memo, and next time return it right away;memo = {} inside the function would wipe the memory on
every call.The check gives the number n. Write fib with memoisation into the dictionary memo
from memo = {} at the top. Print fib(n) and memo: the dictionary shows which numbers
had to be worked out and remembered — every number from 2 to n.
Memoisation is a dictionary outside the function.
First thing, check whether n is in memo — then return the ready one.
The base is n < 2. Otherwise work out the sum of the two before and save it in
memo before returning.