Skip to content
Tutorials Center
My learning

Topics

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.

PHP
function factorial(int $n): int
{
    return $n <= 1 ? 1 : $n * factorial($n - 1);
}
echo factorial(5); // 120

Try it

PHP Recursion over nested arrays

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.

PHP Memoization and depth limits

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 static array, 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(), RecursiveIteratorIterator with RecursiveArrayIterator or RecursiveDirectoryIterator.
  • 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 (isEven calls isOdd and back) works; both functions just need to exist by call time.
  • Return values matter. A forgotten return on the recursive call silently produces null.