← All lessons

Recursion with memoisation

Sign in · Sign up

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]
  • the "version without memory" recalculates the same things over and over — and on fib(50) that already takes very long;
  • memo is a dictionary of results: first check whether it has been worked out already;
  • once worked out, save it in memo, and next time return it right away;
  • the dictionary lives outside: 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.

Hint

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.