Memoization vs Tabulation Approaches

Memoization and tabulation evaluate the same dependency graph

Memoization recursively solves requested states and caches them. Tabulation chooses an order in which dependencies are already available. Both require a correct recurrence and an unambiguous uncomputed marker.

Copy codefun fibonacci(n: Int): Long {
    require(n in 0..92)
    val memo = LongArray(n + 1) { -1 }
    fun solve(k: Int): Long {
        if (k < 2) return k.toLong()
        if (memo[k] != -1L) return memo[k]
        return (solve(k - 1) + solve(k - 2)).also { memo[k] = it }
    }
    return solve(n)
}

This computes each positive non-base state once, giving O(n) work and O(n) cache plus stack space. Bottom-up Fibonacci can reduce workspace to two previous values because older states are no longer needed.

Memoization can avoid unreachable states, while recursion depth can become a limitation. Tabulation often has predictable iteration and locality but may fill unused states.

Exercise

Implement the tabulated and two-variable forms. Compare results across all safe inputs and count state evaluations.

Check: do not use zero as an uncomputed marker when zero is also a legitimate answer.

Further reading: Recursion analysis