PHP, lesson 11
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.
Every recursive function needs two parts:
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.
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 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.
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.
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.
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.
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"; // instant9875245