Recursion Patterns

Also Known As

TL;DR

Explanation

Recursion requires a base case (terminates) and a recursive case (reduces toward base case). Patterns: linear recursion (factorial), tail recursion (optimisable to iteration), tree recursion (Fibonacci naive), mutual recursion (two functions call each other). PHP's default stack depth handles ~few thousand recursive calls; deep recursion needs iteration or explicit stack. Memoisation converts exponential tree recursion to linear. Understanding recursion is prerequisite for tree traversal, graph algorithms, and divide-and-conquer.

Diagram

flowchart TD
    CALL[Function call] --> CHECK{Base case?}
    CHECK -->|yes| RETURN[Return directly<br/>no recursion]
    CHECK -->|no| SMALLER[Recurse with<br/>smaller input]
    SMALLER --> CALL
    subgraph Stack Frames
        F1[fib 5]
        F2[fib 4]
        F3[fib 3]
        F1 --> F2 --> F3
    end
    subgraph Tail Recursion
        TR[Last operation is<br/>the recursive call]
        TR -->|optimised by compiler| LOOP[Converted to loop<br/>no stack growth]
    end
    OVF[Stack overflow] -.->|too many frames| SMALLER
style RETURN fill:#238636,color:#fff
style OVF fill:#f85149,color:#fff
style LOOP fill:#238636,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• No base case or wrong base case — infinite recursion causing stack overflow.
• PHP default stack depth ~few thousand calls — recursing over large directory trees without iteration risks fatal errors.
• Exponential recursion without memoisation — fib(40) makes ~1 billion calls without memoisation.
• Passing large data structures by value in recursive calls — each stack frame copies the data.

Code Examples

// No memoisation — exponential O(2ⁿ):
function fib(int $n): int {
    if ($n <= 1) return $n;
    return fib($n-1) + fib($n-2); // fib(5) calls fib(3) twice, fib(2) thrice...
}
fib(40); // ~1 billion function calls — takes seconds

// Memoised — O(n) with tail recursion alternative:
function fib(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;
    return $memo[$n] ??= fib($n-1, $memo) + fib($n-2, $memo);
}

// Iterative for deep sequences — no stack risk:
function fibIter(int $n): int {
    [$a, $b] = [0, 1];
    for ($i = 2; $i <= $n; $i++) [$a, $b] = [$b, $a+$b];
    return $b;
}

References

• ↗ https://en.wikipedia.org/wiki/Recursion_(computer_science)

Tags

Related Terms