Learn/PHP/11. Recursion
Lesson 11 of 15
Sign in

PHP, lesson 11

Recursion

A recursive function calls itself. It's a natural fit for problems that contain smaller copies of themselves: a folder holds folders, a menu holds sub-menus, and the sum of a list is the first number plus the sum of the rest.

Base case and recursive case

Every recursive function needs two parts:

  1. A base case small enough to answer directly.
  2. A recursive case that shrinks the problem, calls the function on the smaller piece, and uses the answer.

Trace factorial(3): it needs factorial(2), which needs factorial(1), which returns 1. The answers then flow back up: 2 × 1 = 2, then 3 × 2 = 6. Each unfinished call waits on the call stack with its own $n, which is why the values don't overwrite each other.

2 exercises to try what you just read.

Exercise 1

Digital root

Press Ctrl Enter or Check to test your code.

Exercise 2

Staircase paths

Press Ctrl Enter or Check to test your code.

If a call doesn't move closer to the base case, the recursion never ends. PHP keeps adding calls until it runs out of stack or memory and stops with a fatal error, so always check that every path shrinks the input.

Recursion on nested data

Recursion really shines when data is nested to an unknown depth. This function adds up every number in an array whose elements may themselves be arrays:

With plain loops you'd need to know how many levels deep to go. With recursion, each level handles itself.

Remembering answers

Some recursive functions solve the same sub-problem over and over. Naive Fibonacci is the famous example: fib(30) recomputes fib(28) twice, fib(27) three times, and so on, so the work explodes.

The fix is memoisation: store each answer the first time and look it up afterwards. A static array inside the function survives between calls, making it a simple cache:

The ??= operator assigns only when the left side is null or missing, so the expensive expression on the right runs once per $n. Memoisation works whenever a function always returns the same output for the same input.

Recursion versus loops

Anything recursive can be written with a loop and an explicit stack, and loops are a little faster in PHP and can't overflow the call stack. Choose recursion when it makes the code clearer, typically for nested structures and divide-and-conquer algorithms.

Thinking recursively

Don't follow every call in your head. Assume the recursive call already solves the smaller problem correctly, and ask: "given that answer, how do I finish this one?" Then check the base case and that every call shrinks the input.

Further reading

  • User-defined functions
  • Static variables
  • Assignment operators, including ??=

The digital root of a number is found by adding its digits, then adding the digits of the result, and so on until one digit remains. For 9875: 9+8+7+5 = 29, 2+9 = 11, 1+1 = 2.

Write two recursive functions: digitSum(int $n): int (use % 10 and intdiv($n, 10)) and digitalRoot(int $n): int, which keeps applying digitSum until a single digit is left. Read one non-negative whole number and print its digital root.

Sample input:

Sample output:

You can climb stairs one or two steps at a time. Your last move to step n came from step n - 1 or step n - 2, so ways(n) = ways(n - 1) + ways(n - 2), with exactly one way to reach step 0 and one way to reach step 1.

Read n (0 to 90) and print the number of ways to reach the top. Large n is far too slow without memoisation, so cache results in a static array.

Sample input:

Sample output:

<?php

function factorial(int $n): int
{
    if ($n <= 1) {
        return 1;                    // base case
    }
    return $n * factorial($n - 1);   // recursive case
}

echo factorial(5), "\n";   // 120
<?php

function deepSum(array $items): int
{
    $total = 0;
    foreach ($items as $item) {
        $total += is_array($item) ? deepSum($item) : $item;
    }
    return $total;
}

echo deepSum([1, [2, 3], [[4], 5]]), "\n";   // 15
<?php

function fib(int $n): int
{
    static $cache = [];
    if ($n < 2) {
        return $n;
    }
    return $cache[$n] ??= fib($n - 1) + fib($n - 2);
}

echo fib(90), "\n";   // instant
9875
2
4
5