PHP Recursion
In this page:
Introduction to Recursion
A recursive function is one that calls itself, typically to break a problem down into a smaller version of the same problem. Every recursive function needs a base case — a condition where it stops calling itself and just returns a direct answer — or it will keep calling itself indefinitely.
Example: Introduction to Recursion
<?php
function countDown($n) {
if ($n <= 0) {
echo "Done!\n";
return;
}
echo $n . "\n";
countDown($n - 1);
}
countDown(3);
?>Login to try C/C++/Java/PHP code in the editor
Base Case and Recursive Case
The base case is the specific condition that ends the recursion outright, returning a value with no further self-call. The recursive case is everything else: it calls the function again with arguments that are measurably closer to eventually satisfying that base case.
Example: Base Case and Recursive Case
<?php
function factorial($n) {
if ($n <= 1) {
return 1; // base case
}
return $n * factorial($n - 1); // recursive case
}
echo factorial(5);
?>Login to try C/C++/Java/PHP code in the editor
Fibonacci Sequence
Computing the Fibonacci sequence recursively — where each number is the sum of the two before it — mirrors the mathematical definition almost exactly in code, which is exactly why it's such a common first example, even though the naive recursive version is inefficient for large inputs.
Example: Fibonacci Sequence
<?php
function fibonacci($n) {
if ($n <= 1) {
return $n;
}
return fibonacci($n - 1) + fibonacci($n - 2);
}
echo fibonacci(6);
?>Login to try C/C++/Java/PHP code in the editor
Parsing Nested Structures
Recursion suits problems whose depth isn't known ahead of time, like walking a folder tree or a nested category structure — you can't easily predict how many levels deep the nesting goes, so a fixed number of nested loops wouldn't work, but a function calling itself per level does.
Example: Parsing Nested Structures
<?php
function countItems($tree) {
$count = 0;
foreach ($tree as $item) {
$count += is_array($item) ? countItems($item) : 1;
}
return $count;
}
echo countItems(["a", ["b", "c", ["d"]]]);
?>Login to try C/C++/Java/PHP code in the editor
Recursion vs Iteration
Any recursive solution can be rewritten as an iterative one using a loop, and iteration is usually faster and uses less memory, since each recursive call adds a new frame to the call stack. Recursion tends to win on *readability* for naturally self-similar problems, even when it loses on raw performance.
Example: Recursion vs Iteration
<?php
function factorialRecursive($n) {
return $n <= 1 ? 1 : $n * factorialRecursive($n - 1);
}
function factorialIterative($n) {
$result = 1;
for ($i = 2; $i <= $n; $i++) {
$result *= $i;
}
return $result;
}
echo factorialRecursive(5) . " " . factorialIterative(5);
?>Login to try C/C++/Java/PHP code in the editor
Chapter Quiz — Complete all 10 topics to unlock
0/10 topics done
Complete these topics first: