PHP Recursion

Recursion is when a function calls itself to solve a problem by breaking it down into smaller versions of the same problem. Instead of using a loop, a recursive function keeps calling itself with a simpler input until it reaches a case simple enough to answer directly. Recursion is especially useful for problems that are naturally defined in terms of themselves, such as traversing trees, walking directories, or computing mathematical sequences like factorials and Fibonacci numbers.

Overview / How It Works

Every recursive function needs two essential parts: a base case and a recursive case. The base case is the condition under which the function stops calling itself and returns a direct answer. The recursive case is where the function calls itself again, usually with an input that is closer to the base case than the original input was. Without a base case, or with a base case that is never actually reached, a recursive function will call itself forever — or at least until PHP runs out of resources.

Internally, PHP (via the Zend Engine) manages function calls using a call stack. Every time a function is called — recursive or not — PHP pushes a new stack frame onto the call stack. That frame stores the function’s local variables, its parameters, and the point in the calling code it needs to return to. When a recursive function calls itself, a brand new frame is pushed for that call, completely separate from the frame of the call that invoked it. This is why each recursive call has its own independent copy of local variables — a variable named $n in one call does not interfere with $n in another call further down (or up) the stack.

When the base case is finally reached, that innermost call returns a value. That value is handed back to the frame that called it, which uses it to compute its own return value, and so on, unwinding the stack one frame at a time until the original call returns to the code that started the whole process. This “unwinding” is why recursive solutions often read like they build up an answer on the way back out, even though the calls themselves happen on the way in.

Because each call consumes real memory for its stack frame, recursion is not free. PHP (and the underlying C stack it runs on) has a finite limit on how deep this call stack can go. If a recursive function never reaches its base case, PHP will eventually exhaust that stack and either throw a fatal error or, in some configurations, segfault. Tools like Xdebug additionally enforce their own configurable nesting limit (historically defaulting to 256 levels) specifically to catch runaway recursion before it becomes a harder-to-debug crash.

Syntax

There is no special PHP syntax for recursion — any function is recursive simply by calling itself somewhere in its own body.

function functionName(/* parameters */) {
    if (/* base case condition */) {
        return /* direct answer */;
    }

    // recursive case: call the function again with a simpler input
    return functionName(/* smaller/simpler arguments */);
}
  • Base case — the condition checked first that stops further recursion and returns a value without another self-call.
  • Recursive case — the branch where the function calls itself, typically with an argument that is measurably closer to the base case.
  • Return value — each level of recursion usually combines its own work with the result of the recursive call (e.g. $n * factorial($n - 1)).
  • Accumulator parameter (optional) — an extra parameter used to carry a running result down through the calls instead of relying on external or static state.

Examples

Example 1: Factorial

The factorial of a number n (written n!) is the product of all positive integers up to n. It is a classic first recursion example because n! = n * (n-1)!, and 0! and 1! are both defined as 1, giving a clean base case.

<?php
function factorial(int $n): int {
    if ($n <= 1) {
        return 1;
    }
    return $n * factorial($n - 1);
}

echo factorial(5) . "\n";
echo factorial(0) . "\n";
Output:
120
1

Calling factorial(5) triggers calls to factorial(4), factorial(3), factorial(2), and factorial(1), at which point the base case returns 1. That result is multiplied by 2, then 3, then 4, then 5 as the stack unwinds, producing 120.

Example 2: Fibonacci with Memoization

The Fibonacci sequence is defined as fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1. A naive recursive implementation recomputes the same sub-problems many times, so this version passes an array by reference to cache (memoize) results it has already computed.

<?php
function fibonacci(int $n, array &$memo = []): int {
    if ($n <= 1) {
        return $n;
    }
    if (isset($memo[$n])) {
        return $memo[$n];
    }
    return $memo[$n] = fibonacci($n - 1, $memo) + fibonacci($n - 2, $memo);
}

for ($i = 0; $i < 10; $i++) {
    echo fibonacci($i) . ' ';
}
echo "\n";
Output:
0 1 1 2 3 5 8 13 21 34

Each top-level call starts with a fresh $memo array (its default value), but within that single call, the array is passed by reference into every nested recursive call, so previously computed sub-results are reused instead of recomputed. This turns an otherwise exponential-time algorithm into a linear-time one for each top-level call.

Example 3: Flattening a Nested Array

Recursion shines when a data structure can contain itself, such as an array that may hold other arrays at arbitrary depth. This example recursively flattens a multi-dimensional array into a single flat list.

<?php
function flattenArray(array $items): array {
    $result = [];
    foreach ($items as $item) {
        if (is_array($item)) {
            $result = array_merge($result, flattenArray($item));
        } else {
            $result[] = $item;
        }
    }
    return $result;
}

$nested = [1, [2, 3, [4, 5]], 6, [7, [8, [9, 10]]]];
print_r(flattenArray($nested));
Output:
Array
(
    [0] => 1
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 7
    [7] => 8
    [8] => 9
    [9] => 10
)

Whenever foreach encounters an array inside $items, it calls flattenArray() again on that nested array and merges the result in. Because arrays can be nested to any depth, this is much simpler to express recursively than with nested loops of a fixed depth.

How It Works Step by Step

  1. PHP evaluates the function call and pushes a new stack frame containing the arguments and local variables for that call.
  2. The function body runs. If the base case condition is true, it returns immediately — no further recursion happens for that frame.
  3. If the recursive case runs instead, PHP evaluates the recursive call, which pushes yet another frame on top of the current one, and execution pauses in the current frame until that call returns.
  4. This repeats, growing the stack, until some call satisfies the base case and returns a concrete value without recursing further.
  5. Each paused frame resumes exactly where it left off, using the returned value to finish its own computation and return its own result.
  6. The stack unwinds frame by frame until the original, outermost call returns to the caller.

Common Mistakes

Mistake 1: Missing or Unreachable Base Case

If the base case is left out, or the recursive argument never actually reaches it, the function will recurse indefinitely until PHP exhausts its call stack, resulting in a fatal error (or, on some systems, a segmentation fault) instead of a clean result.

<?php
function countdown(int $n): void {
    echo $n . "\n";
    countdown($n - 1);
}

There is no condition that stops the recursion, so calling countdown(3) would keep decrementing forever (3, 2, 1, 0, -1, -2 …) until the stack is exhausted. The fix is to add a base case that actually gets reached:

<?php
function countdown(int $n): void {
    echo $n . "\n";
    if ($n > 0) {
        countdown($n - 1);
    }
}

countdown(3);
Output:
3
2
1
0

Mistake 2: Relying on a static Variable Instead of an Accumulator

A static local variable keeps its value between calls to the same function — including separate, unrelated top-level calls, not just nested recursive ones. Using one as an accumulator silently carries state from a previous call into the next one.

<?php
function sumDigits(int $n): int {
    static $total = 0;
    if ($n === 0) {
        return $total;
    }
    $total += $n % 10;
    return sumDigits(intdiv($n, 10));
}

echo sumDigits(123) . "\n";
echo sumDigits(456) . "\n";
Output:
6
21

The first call correctly sums the digits of 123 (1 + 2 + 3 = 6). But $total is never reset, so the second call starts from 6 instead of 0, producing 21 instead of the correct sum of 456's digits (4 + 5 + 6 = 15). Passing the running total as a parameter avoids the shared state entirely:

<?php
function sumDigits(int $n, int $total = 0): int {
    if ($n === 0) {
        return $total;
    }
    return sumDigits(intdiv($n, 10), $total + $n % 10);
}

echo sumDigits(123) . "\n";
echo sumDigits(456) . "\n";
Output:
6
15

Mistake 3: Naive Recursion That Recomputes the Same Work

A plain recursive Fibonacci function, without memoization, recalculates the same sub-problems an exponential number of times.

<?php
function fibNaive(int $n): int {
    if ($n <= 1) {
        return $n;
    }
    return fibNaive($n - 1) + fibNaive($n - 2);
}

echo fibNaive(30);

This produces the correct value, but computing fibNaive(30) requires well over a million redundant calls because fibNaive(28), for instance, gets recomputed from scratch many times over. As shown in Example 2, caching already-computed results (memoization) fixes this without changing the overall recursive structure.

Best Practices

  • Always write and test the base case first — make sure it is reachable from every recursive path before worrying about the recursive case.
  • Make sure each recursive call moves strictly closer to the base case (a smaller number, a shorter array, a shallower tree), or the recursion may never terminate.
  • Prefer passing state through parameters (accumulators) rather than through static or global variables, which can leak between unrelated calls.
  • Use memoization (caching sub-results, often in an array passed by reference or a class property) whenever a recursive solution recomputes the same inputs repeatedly.
  • Remember that PHP does not perform tail-call optimization, so even a “tail-recursive” function still consumes one stack frame per call — very deep recursion (tens of thousands of levels) can still exhaust the stack.
  • For problems with very deep or unbounded recursion depth (e.g. processing huge flat lists), consider rewriting the solution as an iterative loop with an explicit stack/queue data structure instead.
  • Keep recursive functions focused on one clear problem reduction; if the logic feels tangled, it's often a sign the base case or recursive step needs to be simplified.

Practice Exercises

  1. Write a recursive function reverseString(string $s): string that returns a string reversed, without using PHP's built-in strrev(). Hint: the reverse of a string is its last character followed by the reverse of everything before it.
  2. Write a recursive function arraySum(array $numbers): int|float that returns the sum of all numbers in a flat array by adding the first element to the sum of the rest of the array. What should it return for an empty array?
  3. Write a recursive function power(int $base, int $exponent): int that computes $base raised to $exponent without using the ** operator or pow(). Test it with power(2, 10); it should output 1024.

Summary

  • Recursion is a function calling itself to solve smaller instances of the same problem.
  • Every recursive function needs a reachable base case and a recursive case that progresses toward it.
  • PHP tracks calls on a call stack; each call gets its own frame, and results propagate back as the stack unwinds.
  • Missing or unreachable base cases cause infinite recursion and eventually a fatal error or crash.
  • Naive recursive algorithms can recompute the same work repeatedly; memoization fixes this by caching sub-results.
  • Prefer passing state via parameters over static/global variables to avoid state leaking between calls.
  • PHP has no tail-call optimization, so very deep recursion still has real memory and performance costs — iteration is sometimes the better tool.