Recursion is a programming technique in which a function calls itself to solve a problem. A recursive function needs a base case to stop the repeated calls.
A recursive function calls itself from inside its own definition. Each call works toward a stopping condition.
<?php
function countDown($number) {
if ($number <= 0) {
return;
}
echo $number . "<br>";
countDown($number - 1);
}
countDown(5);
?>5
4
3
2
1The function prints the current number and then calls itself with a smaller number. When the number reaches zero, the function returns without making another call.
The base case is the condition that stops recursion. Without a reachable base case, a recursive function may continue calling itself until PHP encounters a resource or execution limit.
<?php
function printNumber($number) {
if ($number == 1) {
echo "Finished";
return;
}
echo $number . "<br>";
printNumber($number - 1);
}
printNumber(4);
?>4
3
2
When $number becomes 1, the base case
is reached. The function displays "Finished" and
returns.
Notice that the base case is checked before the recursive call.
The factorial of a positive integer is the product of all positive integers from 1 to that number. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.
<?php
function factorial($number) {
if ($number <= 1) {
return 1;
}
return $number * factorial($number - 1);
}
echo factorial(5);
?>120How it works:
factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120This example assumes a non-negative integer input. For a production application, validate the input and consider the limits of factorial calculations.
Recursion can calculate the sum of integers from 1 to a given positive integer.
<?php
function sumNumbers($number) {
if ($number <= 0) {
return 0;
}
return $number + sumNumbers($number - 1);
}
echo sumNumbers(5);
?>15The calculation is:
5 + 4 + 3 + 2 + 1 = 15When the number reaches zero, the function returns zero and the previous calls add their values together.
In the Fibonacci sequence, each number after the first two is the sum of the previous two numbers. This recursive example calculates a Fibonacci number.
<?php
function fibonacci($number) {
if ($number <= 1) {
return $number;
}
return fibonacci($number - 1)
+ fibonacci($number - 2);
}
echo fibonacci(6);
?>8This function uses zero-based positions:
Position: 0 1 2 3 4 5 6
Value: 0 1 1 2 3 5 8This simple recursive implementation repeats many calculations. It is useful for learning recursion, but an iterative or memoized approach is more efficient for larger positions.
Recursion can process array elements one at a time. The function stops when the index reaches the number of elements in the array.
<?php
function displayArray($items, $index = 0) {
if ($index >= count($items)) {
return;
}
echo $items[$index] . "<br>";
displayArray($items, $index + 1);
}
$fruits = ["Apple", "Mango", "Banana", "Orange"];
displayArray($fruits);
?>Apple
Mango
Banana
OrangeEach call displays one array element and increases the index. The recursion stops when no elements remain.
For ordinary array traversal, a
foreach loop is usually simpler.
A string can be reversed recursively by taking its last character and adding the reverse of the remaining string.
<?php
function reverseString($text) {
if (strlen($text) <= 1) {
return $text;
}
return substr($text, -1)
. reverseString(substr($text, 0, -1));
}
echo reverseString("PHP");
?>PHPTry another example:
<?php
echo reverseString("HELLO");
?>OLLEHThis example uses byte-oriented string functions. Multibyte text, such as many Hindi or other Unicode strings, needs a Unicode-aware approach.
Both recursion and loops can repeat operations. Recursion uses function calls, while loops repeat a block of statements.
<?php
function printOneToFive($number) {
if ($number > 5) {
return;
}
echo $number . "<br>";
printOneToFive($number + 1);
}
printOneToFive(1);
?><?php
for ($i = 1; $i <= 5; $i++) {
echo $i . "<br>";
}
?>1
2
3
4
5A loop is generally preferable for simple repetition. Recursion is especially useful when a problem naturally breaks into smaller versions of itself, such as traversing nested structures.
This example calculates a number raised to a non-negative integer power.
<?php
function power($base, $exponent) {
if ($exponent == 0) {
return 1;
}
return $base * power($base, $exponent - 1);
}
echo power(2, 4);
?>16The calculation is:
2 * 2 * 2 * 2 = 16The base case is when the exponent reaches zero. Any non-zero number raised to the power zero returns 1.
This example assumes a non-negative integer exponent.
1. What is recursion?
2. What is the purpose of a base case?
3. What is factorial of 5?