PHP Reference ยท Functions and Classes
Recursion in PHP
Reference for recursion in PHP: base cases, recursive functions on trees and arrays, memoization with static, stack depth limits and converting to iteration.
A recursive function calls itself. Each call works on a smaller piece of the problem until it reaches a case it can answer directly, called the base case. Recursion fits problems that are naturally nested: directory trees, nested arrays, expression parsing, divide-and-conquer algorithms.
Every correct recursive function has two parts: a base case that returns without recursing, and a recursive case that moves toward the base case. If the recursion never reaches the base case, the script runs out of memory or stack.
function factorial(int $n): int { return $n <= 1 ? 1 : $n * factorial($n - 1); } echo factorial(5); // 120
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with fgets(STDIN)), it gets the next line from this box.
Concepts
Base case and recursive case
gcd() above stops when $b is zero (base case) and otherwise calls itself with smaller numbers. Write the base case first; check it handles every input that can reach it, including empty arrays and zero.
Depth and memory
PHP has no built-in recursion limit and does not do tail-call optimization. Each call uses memory on the VM stack, which lives on the heap, so very deep recursion ends with "Allowed memory size exhausted" rather than a stack overflow, usually somewhere in the hundreds of thousands of frames. The Xdebug extension, if loaded, adds a max_nesting_level limit (default 256) that is easy to hit while developing. Depths in the thousands are fine; for millions use a loop.
Recursive closures
An anonymous function cannot refer to itself by name. Capture it by reference (use (&$hanoi)) as in the example, or use an arrow function with a named function instead. A closure can also receive itself as a parameter.
Usage notes
- Duplicated work. The naive Fibonacci recomputes the same values exponentially often. Cache results in a
staticarray, a passed-in array (by reference) or an object property. - Convert to iteration with an explicit stack (an array used with
array_push/array_pop) when depth is unbounded, for example when walking user-supplied nested data. - Built-ins for common cases:
array_walk_recursive(),array_merge_recursive(),array_replace_recursive(),RecursiveIteratorIteratorwithRecursiveArrayIteratororRecursiveDirectoryIterator. - Generators can recurse lazily with
yield from, avoiding building a big array. - Infinite recursion from a missing base case is the most common bug. Add a depth parameter and a guard while debugging.
- Mutual recursion (
isEvencallsisOddand back) works; both functions just need to exist by call time. - Return values matter. A forgotten
returnon the recursive call silently producesnull.