PHP Recursion

Recursion is like standing between two mirrors or opening nested Russian dolls: a function solves a big job by handing a smaller copy of the same job to itself. It stops when the smallest doll is reached.

In this page:

Introduction to Recursion
Base Case and Recursive Case
Fibonacci Sequence
Parsing Nested Structures
Recursion vs Iteration

Syntax

php

function function_name($n) {
    if ($n <= 0) {          // base case
        return base_value;
    }
    return function_name($n - 1);   // recursive case
}

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

<?php
// Define the function `countDown` taking `$n`
function countDown($n) {
    // Check whether `$n <= 0`
    if ($n <= 0) {
        // Print "Done!\n" to the output
        echo "Done!\n";
        // Return early, with no value
        return;
    }
    // Print `$n . "\n"` to the output
    echo $n . "\n";
    // Call `countDown($n - 1)`
    countDown($n - 1);
}
// Call `countDown(3)`
countDown(3);
?>

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

<?php
function factorial($n) {
    if ($n <= 1) {
        return 1; // base case
    }
    return $n * factorial($n - 1); // recursive case
}
echo factorial(5);
?>

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

<?php
// Define the function `fibonacci` taking `$n`
function fibonacci($n) {
    // Check whether `$n <= 1`
    if ($n <= 1) {
        // Return `$n` from this function
        return $n;
    }
    // Return `fibonacci($n - 1) + fibonacci($n - 2)` from this function
    return fibonacci($n - 1) + fibonacci($n - 2);
}
// Print `fibonacci(6)` to the output
echo fibonacci(6);
?>

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

<?php
// Define the function `countItems` taking `$tree`
function countItems($tree) {
    // Declare `$count`, set to `0`
    $count = 0;
    // Loop over `$tree`, binding each item to `$item`
    foreach ($tree as $item) {
        $count += is_array($item) ? countItems($item) : 1;
    }
    // Return `$count` from this function
    return $count;
}
// Print `countItems(["a", ["b", "c", ["d"]]])` to the output
echo countItems(["a", ["b", "c", ["d"]]]);
?>

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

<?php
// Define the function `factorialRecursive` taking `$n`
function factorialRecursive($n) {
    // Return `$n <= 1 ? 1 : $n * factorialRecursive($n - 1)` from this function
    return $n <= 1 ? 1 : $n * factorialRecursive($n - 1);
}
// Define the function `factorialIterative` taking `$n`
function factorialIterative($n) {
    // Declare `$result`, set to `1`
    $result = 1;
    // Classic for-loop: `$i = 2; $i <= $n; $i++`
    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }
    // Return `$result` from this function
    return $result;
}
// Print `factorialRecursive(5) . " " . factorialIterative(5)` to the output
echo factorialRecursive(5) . " " . factorialIterative(5);
?>

Chapter Quiz — Complete all 10 topics to unlock

0/10 topics done

Complete these topics first:

← Previous Lesson PHP Variable Functions Next Lesson → PHP Anonymous Functions