Recursion Patterns
debt(d7/e5/b3/t5)
Closest to 'only careful code review or runtime testing' (d7); phpstan can flag some recursive patterns but stack overflow on deep input typically only surfaces at runtime with real data.
Closest to 'touches multiple files / significant refactor in one component' (e5); quick_fix says convert recursion to iteration with explicit stack — that's a meaningful refactor of the algorithm, not a one-line change.
Closest to 'localised tax' (b3); recursive functions are typically scoped to specific traversal/parsing components rather than load-bearing across the whole system.
Closest to 'notable trap (documented gotcha)' (t5); misconception that recursion is elegant/performant — PHP lacks tail-call optimisation and naive recursion is exponential, a gotcha most devs learn after hitting it.
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;
}