Recursion and dynamic programming — memoization patterns

Advanced5 min read·eng-08-004

interview

Concept

Recursion: A function that calls itself. Every recursive solution has:

Base case: The condition that stops recursion (no more calls).
Recursive case: The problem broken into a smaller version of itself.

Call stack: Each recursive call adds a frame to the call stack. Too many frames → stack overflow. PHP's default stack is ~8MB. Deep recursion (1000+ levels) can exhaust it.

Tail recursion: When the recursive call is the last operation in the function. PHP does NOT optimize tail recursion (TCO). Convert to iteration for deep recursion.

Dynamic Programming (DP): Recursion + memoization. Avoid recomputing the same subproblems by caching results.

Memoization (top-down DP): Add a cache. Before computing, check the cache. After computing, store the result.

Tabulation (bottom-up DP): Solve subproblems from the smallest first, fill a table. No recursion — just loops. More memory-efficient (no call stack), harder to write intuitively.

Classic DP problems: Fibonacci, coin change, longest common subsequence, knapsack, edit distance.

When to use DP:

Problem has overlapping subproblems: Same computation needed multiple times.
Problem has optimal substructure: Optimal solution built from optimal sub-solutions.

Greedy vs DP: Greedy makes the locally optimal choice at each step and never looks back. DP explores all possibilities and remembers optimal choices. Greedy is faster but wrong for many problems (works for: Dijkstra, Huffman, interval scheduling).

Code Example

php

<?php
// Naive recursive Fibonacci — O(2^n) time (terrible)
function fib(int $n): int
{
    if ($n <= 1) return $n;
    return fib($n - 1) + fib($n - 2); // fib(5) calls fib(4) and fib(3)
}                                       // fib(4) calls fib(3) and fib(2) — fib(3) computed TWICE!

// Memoized Fibonacci — O(n) time, O(n) space
function fibMemo(int $n, array &$memo = []): int
{
    if ($n <= 1)       return $n;
    if (isset($memo[$n])) return $memo[$n]; // cache hit — skip recomputation
    $memo[$n] = fibMemo($n - 1, $memo) + fibMemo($n - 2, $memo);
    return $memo[$n];
}

echo fibMemo(50); // 12586269025 (instant — without memo, this would take years)

// Tabulated Fibonacci — O(n) time, O(1) space (just two variables)
function fibTab(int $n): int
{
    if ($n <= 1) return $n;
    $prev = 0; $curr = 1;
    for ($i = 2; $i <= $n; $i++) {
        [$prev, $curr] = [$curr, $prev + $curr];
    }
    return $curr;
}

// Coin change — minimum coins to make $amount (DP, bottom-up)
function coinChange(array $coins, int $amount): int
{
    $dp = array_fill(0, $amount + 1, PHP_INT_MAX); // dp[i] = min coins for amount i
    $dp[0] = 0; // 0 coins needed for amount 0

    for ($a = 1; $a <= $amount; $a++) {
        foreach ($coins as $coin) {
            if ($coin <= $a && $dp[$a - $coin] !== PHP_INT_MAX) {
                $dp[$a] = min($dp[$a], $dp[$a - $coin] + 1);
            }
        }
    }
    return $dp[$amount] === PHP_INT_MAX ? -1 : $dp[$amount];
}

echo coinChange([1, 5, 10, 25], 41); // 3 (25 + 10 + 5 + 1? No: 25+10+5+1=4? Actually 25+10+5+1=41 = 4 coins, or 25+16=no... 25+10+5+1 = 4)

// Longest Common Subsequence (LCS) — classic DP
function lcs(string $a, string $b): int
{
    $m  = strlen($a); $n = strlen($b);
    $dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

    for ($i = 1; $i <= $m; $i++) {
        for ($j = 1; $j <= $n; $j++) {
            if ($a[$i - 1] === $b[$j - 1]) $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
            else                             $dp[$i][$j] = max($dp[$i - 1][$j], $dp[$i][$j - 1]);
        }
    }
    return $dp[$m][$n];
}

echo lcs('ABCBDAB', 'BDCAB'); // 4 ("BCAB" or "BDAB")

PreviousBinary search — O(log n) lookups on sorted dataAlgorithms in PHP NextTwo-pointer and sliding window — common interview patternsAlgorithms in PHP