Memoized recursion

Overview

Some recursions revisit the same subproblem an exponential number of times. Memoization fixes that with a cache: before computing f(n), check whether it has already been solved; after computing it, store the result. The generalised staircase — count the ways to climb n steps taking 1..max_step at a time — is the clean example, because the naive recursion is genuinely exponential and one array turns it linear. The lesson's companion, counting phone-keypad letter combinations, is the contrast: it has no overlapping subproblems, so memoization would add complexity and buy nothing.

Why it matters

Memoization is the bridge between a brute-force recursion you can write confidently and a solution that actually finishes. It is usually the fastest path to a correct efficient algorithm: write the obvious recursion, add a cache, done — no need to work out the bottom-up dependency order first. Recognising when it does not apply is equally valuable.

Core concepts

The pattern. Three lines around the existing recursion: a sentinel-initialised cache, a lookup on entry, and a store before returning.

Choose a sentinel that cannot be a real answer. -1 works when all results are non-negative. Zero-initialising is a classic mistake when 0 is a legitimate result — the cache then permanently returns 0 for those states.

Initialise the cache once. Filling it inside the recursive function resets it on every call. Allocate and fill in a wrapper, then call the memoised helper.

State must fully determine the answer. The cache is keyed by the parameters that vary. If a result depends on something not in the key, the cache returns a wrong answer for a different context — a subtle and painful bug.

When memoization does not help. If every recursive call is on a distinct state — as in enumerating letter combinations, where each path is unique — there is nothing to reuse. Overlap is the precondition.

Top-down vs bottom-up. Memoization is top-down DP. It keeps the natural recursion (easy to derive) at the cost of call overhead and stack depth; tabulation reverses both trade-offs.

Syntax notes

#include <stdlib.h>

/* ways to climb n steps taking 1..ms at a time; memo[] pre-filled with -1 */
long long stair(int n, int ms, long long *memo) {
    if (n == 0) return 1;              /* one way to stand still */
    if (n < 0)  return 0;              /* overshot */
    if (memo[n] >= 0) return memo[n];  /* CACHE HIT */
    long long t = 0;
    for (int s = 1; s <= ms; s++) t += stair(n - s, ms, memo);
    return memo[n] = t;                /* store BEFORE returning */
}

/* wrapper: allocate and seed the cache exactly once */
long long climb_ways(int n, int ms) {
    if (n < 0) return 0;
    long long *memo = malloc((size_t)(n + 1) * sizeof *memo);
    if (!memo) return -1;
    for (int i = 0; i <= n; i++) memo[i] = -1;   /* sentinel, not 0 */
    long long r = stair(n, ms, memo);
    free(memo);
    return r;
}

Key points:

• -1 as the sentinel because every real answer is non-negative.
• The cache is seeded in the wrapper, never inside the recursive function.
• return memo[n] = t; both stores and returns — a common and readable idiom.

Lesson

Some recursions revisit the same subproblem exponentially often. Memoization caches each result so it's computed once — the generalized staircase (1..max_step) needs it, while phone letter combinations count by the multiplication principle.

Code examples

#include <stdio.h>
#include <stdlib.h>
static long long stair(int n,int ms,long long*memo){ if(n==0) return 1; if(n<0) return 0; if(memo[n]>=0) return memo[n]; long long t=0; for(int s=1;s<=ms;s++) t+=stair(n-s,ms,memo); return memo[n]=t; }
static long long letters(const char*d){ if(!*d) return 0; long long p=1; for(;*d;d++){ char c=*d; int L=(c=='7'||c=='9')?4:(c>='2'&&c<='9')?3:0; if(!L) return 0; p*=L; } return p; }
int main(void){
    long long memo[13]; for(int i=0;i<13;i++) memo[i]=-1;
    printf("ways to climb 12 stairs (1..3 steps) = %lld\n", stair(12,3,memo));
    printf("letter combinations of \"259\" = %lld\n", letters("259"));
    return 0;
}

Line by line

Common mistakes

Omitting the cache (times out); mis-mapping keypad digits to letter counts.

Debugging tips

Compiler errors and warnings:

• -Wmaybe-uninitialized if the cache is allocated with malloc and you forget the seeding loop.
• No warning for a wrong sentinel.

Runtime symptoms:

• Still exponentially slow. The cache is never read (missing the lookup), or it is re-initialised on every call because the seeding loop sits inside the recursive function.
• Everything returns 0. The cache was zero-initialised with calloc and 0 is being treated as a stored answer. Use a sentinel that cannot occur.
• Wrong answers that vary by call order. The cache key does not capture all the state the result depends on.
• Garbage results. malloc without the seeding loop — the cache is full of indeterminate values that happen to be >= 0.
• Crash for n = 0. The allocation must be n + 1 entries; index n must be valid.

Technique: count the number of actual computations (increment a counter just past the cache check). For memoised staircase it should be about n; if it grows exponentially the cache is not working.

Memory safety

• calloc is the wrong choice here. Zero is a legitimate answer for some states, so a zero-filled cache is indistinguishable from a stored result. Use malloc plus an explicit sentinel loop, or a separate seen[] flag array.
• malloc without seeding is worse — the cache contains indeterminate values, and reading them to make decisions is undefined behaviour.
• Allocation size. n + 1 entries because index n is used; validate n >= 0 before the cast to size_t.
• Ownership. The wrapper allocates and frees; the recursive helper only borrows. Mixing those responsibilities leads to double frees or leaks.
• Depth is still O(n). Memoization removes redundant work, not stack depth — a very large n can still overflow the stack. Bottom-up tabulation avoids that entirely.
• Free on every path, including the error path.

Real-world uses

Concrete uses: Memoization is how you make a recursive parser, a route planner over a DAG, or a game-tree evaluator practical. Compilers memoise type inference results; build systems cache subtree results; web frameworks memoise resolved templates. Any time you write a clean recursion that is too slow, a cache is the first thing to try.

Professional best practices:

Beginner:

• Write the plain recursion first, confirm it is correct, then add the cache.
• Pick a sentinel that cannot be a valid answer.

Intermediate:

• Seed the cache in a wrapper so it is initialised exactly once.
• Make sure the cache key contains every varying parameter the answer depends on.
• If the recursion depth is a concern, convert the memoised version to bottom-up tabulation — the recurrence is already worked out by then.

Practice tasks

1. (Beginner) Naive staircase. Implement the uncached recursion and time it for n = 40, ms = 2. Concepts: exponential recomputation.

2. (Beginner) Add memoization. Add the cache with a -1 sentinel seeded in a wrapper, and re-time it. Example: climb_ways(5,2) -> 8. Concepts: the three-line pattern.

3. (Intermediate) Count computations. Instrument both versions with a counter and compare for n = 30. Concepts: measuring the benefit.

4. (Intermediate) Where it does not help. Implement the phone-keypad letter-combination count and explain why memoization adds nothing. Concepts: recognising when subproblems do not overlap.

Summary

Memoization turns an exponential recursion into a linear one with three additions: a cache seeded to a sentinel, a lookup on entry, and a store before returning. Choose the sentinel so it cannot collide with a real answer — zero-filling is the classic bug when 0 is a valid result — and seed the cache in a wrapper so it is initialised exactly once rather than on every recursive call. The technique only pays when subproblems genuinely overlap; when every call is a distinct state, as in enumerating letter combinations, a cache is pure overhead. Note that memoization removes redundant work but not stack depth.

Practice with these exercises

• Generalized staircase
• Phone letter combinations