From Recursion to Dynamic Programming

I was working on a Fibonacci problem and hit a classic performance wall. The recursive solution was elegant but painfully slow for larger inputs.

The naive recursive approach

func fib(n int) int {
    if n < 2 {
        return n
    }
    return fib(n-1) + fib(n-2)
}

Works for small n, but fib(40) takes forever. Why? The same subproblems get calculated over and over.

Adding memoization

The fix is simple: cache results. This turns exponential complexity into linear.

func fibMemo(n int, memo map[int]int) int {
    if val, found := memo[n]; found {
        return val
    }
    if n < 2 {
        memo[n] = n
        return n
    }
    result := fibMemo(n-1, memo) + fibMemo(n-2, memo)
    memo[n] = result
    return result
}

What clicked for me

What's interesting is how this changes your thinking. Instead of just solving the problem, you start thinking about what work you can reuse. This pattern shows up everywhere - once you see it, you can't unsee it.

Dynamic programming isn't just about clever algorithms - it's about avoiding redundant work. Sometimes the optimization is as simple as adding a cache.

Good reminder that the most elegant solution isn't always the most practical!