1. Concept library
  2. Data Structures & Algorithms
  3. Module 6: Recursion and backtracking

Concept

Memoisation

Memoisation caches the result of a function for each input, so a recursion that would recompute the same subproblems many times computes each once. It turns exponential time into polynomial time.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain how a cache turns repeated subproblems into single computations
  2. Add memoisation to a recursive function and compare its running time
  3. Spot a cache key that includes something irrelevant and never repeats

In practice

A few lines that show Memoisation doing its job.

Python
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(80)          # instant; without the cache it never finishes

def climb(n, memo={}):          # the hand-rolled version
    if n <= 1: return 1
    if n not in memo:
        memo[n] = climb(n - 1) + climb(n - 2)
    return memo[n]

The common mistake

Watch for

Memoising a function whose arguments include something irrelevant to the result, such as an index and a copy of the whole list. The cache key never repeats and nothing is saved.

What to know first

Your roadmap puts these before Memoisation, unless you already know them.

How it stays learned

Once a session shows you understand Memoisation, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled

Where it leads

Topics that build on Memoisation.

Previous in the module← Backtracking templates