Know this before you start: “Recursion first, then remember answers (memoization)”

Memoization: recursion that remembers

Write the natural recursion, then cache each result so repeated calls become lookups. Exponential often becomes linear.

The idea

Many recursive solutions solve the same smaller problem again and again. fib(5) calls fib(3) twice and fib(2) three times; for bigger n it explodes.

Memoization stores each answer the first time it's computed and returns it from the cache afterwards. In Python, @functools.cache does it in one line.

This is top-down dynamic programming: it's often the easiest way to get a correct DP, because you write the recursion first.

See it step by step

Ways to climb 5 stairs, 1 or 2 at a time

ways(n) = ways(n − 1) + ways(n − 2); ways(0) = ways(1) = 1
Without a cache, ways(2) is computed 3 times inside ways(5).
With one, each of ways(0…5) is computed once: 1, 1, 2, 3, 5, 8 → 8.

In code (Python)

from functools import cache

@cache
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

def ways_manual(n, memo=None):
    memo = {} if memo is None else memo
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = ways_manual(n - 1, memo) + ways_manual(n - 2, memo)
    return memo[n]

print(ways(5), ways(40))          # 8 165580141
print(ways_manual(5))             # 8

O(number of distinct calls × work per call). Here O(n).

When you'll use it

Your recursion repeats the same arguments: counting ways, minimum cost, can-I-reach problems.

Common mistakes

Caching on mutable arguments like lists (they can't be dictionary keys).
Hitting Python's recursion limit on very deep inputs.