Recursive Functions

Ma Mahalakshmi V Updated 14 Nov 2026
7 min read ·Lesson 72 of 256

What Is a Recursive Function?

In simple terms: A recursive function is a function that calls itself to solve a smaller version of the same problem, until the problem becomes so small that the answer is obvious.

Technically: Recursion is a technique in which a function's body contains a call to the same function. Each call gets its own set of local variables on the call stack. A correct recursive function always has:

  1. A base case — a condition where it returns a result without calling itself.
  2. A recursive case — where it calls itself with input that moves closer to the base case.

Why Recursion Is Useful

Some data is naturally self-similar: a category contains subcategories, which contain subcategories; a folder contains folders; a comment has replies, which have replies; a JSON document contains nested arrays. For such structures, a recursive function often mirrors the shape of the data and is much simpler than an equivalent loop.


A First Example: Factorial

The factorial of n (written n!) is n × (n − 1) × … × 1. It can be defined recursively:

  • 1! = 1 (base case)
  • n! = n × (n − 1)! (recursive case)
<?php
function factorial(int $n): int
{
    if ($n <= 1) {
        return 1;                       // base case
    }

    return $n * factorial($n - 1);      // recursive case
}

echo factorial(5) . "\n";
echo factorial(1) . "\n";

Output

120
1

How the Calls Unfold

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)))       ← base case reached
= 120
  1. Each call waits for the result of the next call.
  2. When factorial(1) reaches the base case, it returns 1 without recursing.
  3. The waiting calls then complete in reverse order, multiplying as they return.

The Call Stack

Every function call is placed on the call stack, a memory area that records where each call should return to and stores its local variables. Each recursive call adds a new frame to the stack; each return removes one.

You can watch this happen by tracing the calls:

<?php
function countdown(int $n, int $depth = 0): void
{
    $indent = str_repeat('  ', $depth);

    if ($n === 0) {
        echo "{$indent}Liftoff!\n";
        return;
    }

    echo "{$indent}Entering countdown($n)\n";
    countdown($n - 1, $depth + 1);
    echo "{$indent}Leaving countdown($n)\n";
}

countdown(3);

Output

Entering countdown(3)
  Entering countdown(2)
    Entering countdown(1)
      Liftoff!
    Leaving countdown(1)
  Leaving countdown(2)
Leaving countdown(3)

The "Leaving" lines appear in reverse order because each call only finishes after the call it made has finished. Code after the recursive call runs on the way back up.


Recursion With Nested Data

Summing a Nested Array

<?php
function nestedSum(array $values): int|float
{
    $total = 0;

    foreach ($values as $value) {
        if (is_array($value)) {
            $total += nestedSum($value);   // recursive case: go deeper
        } else {
            $total += $value;              // base case: a plain number
        }
    }

    return $total;
}

echo nestedSum([1, [2, 3], [4, [5, 6]], 7]) . "\n";

Output

28

The function does not need to know how deep the nesting goes. Whenever it meets an array, it hands that array to a new call of itself.

Flattening a Nested Array

<?php
function flatten(array $values): array
{
    $result = [];

    foreach ($values as $value) {
        if (is_array($value)) {
            $result = [...$result, ...flatten($value)];
        } else {
            $result[] = $value;
        }
    }

    return $result;
}

echo implode(', ', flatten([1, [2, 3], [4, [5, [6]]], 7])) . "\n";

Output

1, 2, 3, 4, 5, 6, 7

Each nested array is flattened by a recursive call, and the results are combined with the spread operator.


Practical Example: Category Tree

Online shops store categories in a database table where each category has an optional parent. Displaying them as a tree is a classic recursive task.

<?php
$categories = [
    ['id' => 1, 'name' => 'Electronics', 'parent' => null],
    ['id' => 2, 'name' => 'Laptops', 'parent' => 1],
    ['id' => 3, 'name' => 'Gaming Laptops', 'parent' => 2],
    ['id' => 4, 'name' => 'Phones', 'parent' => 1],
    ['id' => 5, 'name' => 'Books', 'parent' => null],
];

function printTree(array $categories, ?int $parentId = null, int $depth = 0): void
{
    foreach ($categories as $category) {
        if ($category['parent'] === $parentId) {
            echo str_repeat('  ', $depth) . '- ' . $category['name'] . "\n";
            printTree($categories, $category['id'], $depth + 1);
        }
    }
}

printTree($categories);

Output

- Electronics
  - Laptops
    - Gaming Laptops
  - Phones
- Books

Step-by-Step Explanation

  1. The first call looks for top-level categories (parent === null): Electronics and Books.
  2. For each category found, the function prints it and calls itself with that category's ID as the new parent, one level deeper.
  3. The base case is implicit: when no categories have the given parent, the loop prints nothing and the call returns.
  4. $depth controls indentation, increasing by one level with each recursive call.

This version scans the whole list in every call, which is fine for a few hundred categories. For large trees, group categories by parent first ($byParent[$parentId][] = $category) so each call only loops over its own children.


Fibonacci and the Cost of Repeated Work

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, …) is defined recursively, but a direct recursive implementation is very slow:

<?php
function fibonacci(int $n): int
{
    if ($n < 2) {
        return $n;
    }

    return fibonacci($n - 1) + fibonacci($n - 2);
}

echo fibonacci(10) . "\n";

Output

55

Each call makes two more calls, and the same values are calculated again and again: fibonacci(30) already needs more than a million calls. Two common fixes:

  • Memoization: remember results that have already been calculated, for example in a static array (see Static Variables, which includes a memoized Fibonacci example).
  • Iteration: a simple loop that keeps the last two values computes the result in n steps.

Recursion is elegant, but always consider how many calls it will make.


Recursion Depth and Its Limits

Each recursive call uses memory on the call stack. Recursing too deeply — for example, because the base case is never reached — eventually fails.

function broken(int $n): int
{
    return broken($n - 1);   // no base case: never stops
}

What happens depends on the configuration:

  • PHP 8.3+ detects deep recursion and throws an Error such as "Maximum call stack size of … reached. Infinite recursion?" (controlled by the zend.max_allowed_stack_size setting).
  • Older versions may exhaust memory_limit or crash the process.
  • With the Xdebug extension enabled, recursion is stopped earlier by its nesting limit (xdebug.max_nesting_level).

PHP does not optimize tail recursion, so even a correct recursive function can fail for very deep inputs (for example, a recursion depth of hundreds of thousands). For long linear sequences, use a loop; reserve recursion for tree-shaped data whose depth is naturally limited.

Converting Recursion to Iteration

<?php
function factorialIterative(int $n): int
{
    $result = 1;

    for ($i = 2; $i <= $n; $i++) {
        $result *= $i;
    }

    return $result;
}

echo factorialIterative(5) . "\n";

Output

120

The loop version uses constant stack space. For tree structures, the iterative equivalent needs an explicit stack (an array of items still to process), which is usually less readable than recursion.


When to Use Recursion

Use Recursion WhenPrefer a Loop When
Data is tree-shaped or nested (categories, folders, menus, comments, JSON)Processing a flat list
The depth is naturally limited (tens or hundreds of levels)The depth can be very large
The recursive version is clearly simplerThe iterative version is equally clear

Related built-in tools: array_walk_recursive() applies a function to every leaf value of a nested array, and RecursiveIteratorIterator with RecursiveDirectoryIterator walks directory trees.


Common Mistakes

Missing or Unreachable Base Case

Effect: Infinite recursion and a stack overflow error.

Fix: Define the base case first, and make sure every recursive call moves closer to it (for example, $n - 1, a smaller array, or a child node).

Not Returning the Recursive Result

function factorial(int $n): int
{
    if ($n <= 1) {
        return 1;
    }
    $n * factorial($n - 1);   // result calculated but not returned
}

Fix: return $n * factorial($n - 1);.

Repeating the Same Work

Effect: Exponential running time (as in naive Fibonacci).

Fix: Memoize results or use iteration.

Using Recursion for Very Deep Linear Problems

Effect: Stack overflow on large inputs.

Fix: Use a loop.


Best Practices

  • Write the base case first and keep it obvious.
  • Make each recursive call work on a strictly smaller problem.
  • Use recursion for naturally nested data with limited depth.
  • Memoize or iterate when the same subproblems repeat.
  • Pass depth or path information as parameters when you need indentation or limits.

Official reference: https://www.php.net/manual/en/functions.user-defined.php

0 Comments

Reviewed before they appear

No comments yet.

PHP
PHP Tutorial Index PHP Home PHP Intro PHP Install PHP Built-in Web Server PHP Syntax PHP Tags PHP and HTML PHP Comments PHP Multiline Comments PHP Variables Variables Scope Static Variables Variable Variables PHP Echo / Print PHP printf / sprintf PHP Data Types PHP Booleans PHP NULL PHP Strings String Functions Modify Strings Concatenate Strings Slicing Strings Escape Characters String Interpolation Heredoc and Nowdoc Search in Strings Multibyte Strings PHP Floats PHP Casting PHP Type Juggling PHP Math PHP Random Numbers PHP Constants PHP Magic Constants PHP Operators Arithmetic Operators Assignment Operators Comparison Operators Increment / Decrement Operators Logical Operators Null Coalescing Operator Spaceship Operator Operator Precedence PHP If...Else...Elseif PHP If PHP If Operators PHP If...Else PHP Shorthand if PHP Nested if PHP Switch PHP Match Alternative Syntax PHP Loops While Loop Do While Loop For Loop Foreach Loop Nested Loops Break Statement Continue Statement PHP Functions User-defined Functions Function Arguments Default Argument Values Pass by Reference Named Arguments Variadic Functions Return Values Type Declarations in Functions Recursive Functions Variable Functions Anonymous Functions Closures Arrow Functions First-class Callable Syntax PHP Arrays Indexed Arrays Associative Arrays Create Arrays Access Array Items Update Array Items Add Array Items Remove Array Items Sorting Arrays Multidimensional Arrays Array Destructuring Array Spread Operator Search in Arrays Merge Arrays array_map / array_filter / array_reduce Array Functions PHP Superglobals $GLOBALS $_SERVER $_REQUEST $_POST $_GET $_FILES $_COOKIE $_SESSION \$\_ENV PHP RegEx RegEx Patterns RegEx Modifiers preg_match preg_replace preg_split PHP RegEx Functions PHP Form Handling PHP Form Validation PHP Form Required PHP Form URL/E-mail Form Input Sanitizing Escaping Output (htmlspecialchars) Checkbox, Radio and Select Inputs Sticky Forms PHP Form Complete PHP Date and Time Date Formatting DateTime Class Timezones PHP Include Include vs Require PHP File Handling PHP File Open/Read PHP File Create/Write File Delete / Rename / Copy PHP Directories PHP CSV Files PHP File Upload PHP Cookies PHP Sessions PHP Filters PHP Filters Advanced PHP Callback Functions PHP JSON PHP Exceptions Error Handling Custom Error Handler Error Logging HTTP Headers and Redirects Output Buffering Sending Email PHP cURL Consuming REST APIs PHP Generators PHP What is OOP PHP Classes/Objects The $this Keyword PHP Properties PHP Methods PHP Constructor Constructor Property Promotion PHP Destructor PHP Access Modifiers Readonly Properties PHP Inheritance Method Overriding The final Keyword PHP Class Constants PHP Abstract Classes PHP Interfaces Polymorphism PHP Traits PHP Static Methods PHP Static Properties Late Static Binding Magic Methods Object Cloning Comparing Objects Anonymous Classes PHP Enums PHP Namespaces Autoloading Classes PHP Iterables Iterators Object Serialization Strict Types Union Types Nullable Types Mixed and Never Types Nullsafe Operator PHP Attributes PHP Fibers Readonly Classes Property Hooks (PHP 8.4) Asymmetric Visibility (PHP 8.4) Reflection API SPL Data Structures MySQL Database MySQL Connect MySQL Create DB MySQL Create Table MySQL Insert Data MySQL Get Last ID MySQL Insert Multiple MySQL Prepared MySQL Select Data MySQL Where MySQL Order By MySQL Delete Data MySQL Update Data MySQL Limit Data MySQL Joins with PHP Pagination with PHP PDO Introduction PDO Connect PDO Prepared Statements PDO Fetch Modes PDO Transactions PDO Error Handling PHP XML Parsers PHP SimpleXML Parser PHP SimpleXML - Get PHP XML Expat Parser PHP DOM Parser PHP XMLReader PHP XMLWriter AJAX Intro AJAX PHP AJAX Database AJAX XML AJAX Live Search AJAX Poll AJAX with JSON Security Introduction Password Hashing SQL Injection Prevention XSS Prevention CSRF Protection Session Security Secure Cookies File Upload Security Filesystem Security Error Reporting in Production Hiding PHP Encryption with Sodium PHP Configuration (php.ini) PHP Command Line (CLI) Composer PSR-4 Autoloading Installing Extensions (PECL / PIE) Debugging PHP OPcache & Performance Garbage Collection PHP-FPM Migrating to PHP 8 Project: Contact Form with Email Project: Login & Registration System Project: CRUD App with MySQL Project: Image Upload Gallery Project: Shopping Cart with Sessions Project: Simple Blog Project: REST API with PHP
Ask about this post
AI Ask about this post

Ask questions about Recursive Functions and get answers drawn from it.

Signed-in readers only.