Fibonacci with Memoization

Compute fib(n) recursively. Cache each fib(k) in a memo array so each subproblem is solved at most once.

Algorithm

Canonical input n = 6 produces fib(6) = 8. Replay highlights every memo write and every cache hit.

Basic Implementation

basic.c

#include <stdio.h>
#include <stdbool.h>

#define MEMO_SIZE 16

static int memo_value[MEMO_SIZE];
static bool memo_seen[MEMO_SIZE];

int fib(int n) {
    if (memo_seen[n]) {
        return memo_value[n];
    }
    if (n < 2) {
        memo_value[n] = n;
        memo_seen[n] = true;
        return n;
    }
    int value = fib(n - 1) + fib(n - 2);
    memo_value[n] = value;
    memo_seen[n] = true;
    return value;
}

int main(void) {
    int result = fib(6);
    printf("%d\n", result);
    printf("{");
    bool first = true;
    for (int i = 0; i < MEMO_SIZE; ++i) {
        if (memo_seen[i]) {
            if (!first) printf(", ");
            printf("%d: %d", i, memo_value[i]);
            first = false;
        }
    }
    printf("}\n");
    return 0;
}

Complexity

Time: O(n) with memoization (vs. O(2^n) without)
Space: O(n) memo + O(n) call stack

Implementation notes

C: file-scope int memo_value[MEMO_SIZE] and bool memo_seen[MEMO_SIZE] from <stdbool.h> give the memo a deterministic iteration order keyed by n, which keeps the final printout honest without leaning on a hash-map container the standard library does not provide.
The replay shows the call stack on one side and the memo map on the other so memo writes and cache hits are visually distinct.

memoization A parallel `memo_value[]` / `memo_seen[]` pair indexed by `n` stores each completed subproblem. Before recursing, check `memo_seen[n]`: a hit returns immediately, a miss descends.

explicit memo state The memo lives in file-scope static arrays so the recursion stays about caching, not parameter passing — C does not need a heap map container for small `n`.