PHP Recursive Functions Tutorial with Examples

A recursive function is a function that calls itself to solve smaller instances of a larger problem. This technique is useful for breaking down complex tasks into simpler sub-tasks.

Recursive functions are commonly used in mathematical computations, directory traversal, and tree data structures.

This tutorial covers:

1. Understanding Recursion

A recursive function has two main components:

1. Base Case – The condition that stops the recursion.
2. Recursive Case – The function calls itself with a modified argument.

Basic Syntax of a Recursive Function

function recursiveFunction($param) {
    if (base_condition) {
        return; // Stop recursion
    } else {
        recursiveFunction(modified_param); // Recursive call
    }
}

2. Writing a Basic Recursive Function

Example: Countdown using Recursion

function countdown($number) {
    if ($number <= 0) { // Base case
        echo "Done!\n";
        return;
    }
    
    echo "$number\n";
    countdown($number - 1); // Recursive call
}

countdown(5);

Output

5
4
3
2
1
Done!

Explanation

• The function calls itself with ($number – 1), reducing the number each time.
• When $number reaches 0, it stops the recursion.

3. Factorial Calculation Using Recursion

The factorial of a number (n!) is defined as:
n!=n×(n−1)!n! = n \times (n-1)!
For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Example: Recursive Factorial Function

function factorial($n) {
    if ($n <= 1) { // Base case
        return 1;
    }
    return $n * factorial($n - 1); // Recursive call
}

echo factorial(5); // Output: 120

Explanation

• The base case is if ($n <= 1) return 1;
• The recursive case is return $n * factorial($n – 1);.

4. Generating Fibonacci Numbers Using Recursion

The Fibonacci sequence follows the rule:
F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)
With base cases:

• F(0)=0F(0) = 0
• F(1)=1F(1) = 1

Example: Recursive Fibonacci Function

function fibonacci($n) {
    if ($n == 0) return 0;
    if ($n == 1) return 1;

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

echo fibonacci(6); // Output: 8

Explanation

• The function calls itself twice (fibonacci($n – 1) and fibonacci($n – 2)).
• This recomputes values multiple times, making it inefficient for large numbers.

Optimization Tip: Use memoization or iteration to improve performance.

5. Recursive Directory Traversal

Recursion is useful for listing files and directories.

Example: List Files in a Directory Recursively

function listFiles($dir) {
    $files = scandir($dir);

    foreach ($files as $file) {
        if ($file == "." || $file == "..") continue;

        $filePath = $dir . DIRECTORY_SEPARATOR . $file;
        
        if (is_dir($filePath)) {
            echo "Directory: $filePath\n";
            listFiles($filePath); // Recursive call
        } else {
            echo "File: $filePath\n";
        }
    }
}

listFiles("example_directory");

Explanation

• scandir($dir) lists files and directories.
• Skips “.” and “..” entries.
• Calls listFiles($filePath) if it finds a directory.

Use Case: Processing large folder structures, like in backup scripts.

6. Recursion with Associative Arrays

Recursion can also be used for nested arrays (e.g., JSON, menus, trees).

Example: Recursively Print Nested Arrays

function printNestedArray($arr, $indent = 0) {
    foreach ($arr as $key => $value) {
        echo str_repeat(" ", $indent) . "$key: ";

        if (is_array($value)) {
            echo "\n";
            printNestedArray($value, $indent + 4); // Recursive call with indentation
        } else {
            echo "$value\n";
        }
    }
}

$data = [
    "name" => "Alice",
    "age" => 25,
    "address" => [
        "city" => "New York",
        "zip" => "10001",
        "country" => [
            "name" => "USA",
            "code" => "US"
        ]
    ]
];

printNestedArray($data);

Output

name: Alice
age: 25
address: 
    city: New York
    zip: 10001
    country: 
        name: USA
        code: US

Explanation

• Loops through the array using foreach.
• If value is an array, calls itself with increased indentation.
• Works for deeply nested structures.

Use Case: Processing JSON, XML, nested configurations, menu structures.

7. Best Practices for Recursive Functions

1. Always Include a Base Case

A recursive function must have a stopping condition to avoid infinite recursion.
Bad Example (No base case, causes infinite recursion)

function infiniteRecursion() {
    echo "Infinite loop!\n";
    infiniteRecursion(); // No stopping condition
}

Good Example

function safeRecursion($n) {
    if ($n <= 0) return; // Base case
    echo "$n\n";
    safeRecursion($n - 1);
}

2. Avoid Deep Recursion

Excessive recursion can cause stack overflow errors.
For example, calling factorial(10000) will exceed the PHP recursion limit.

To check the recursion limit:

echo ini_get('max_execution_time');  // Execution time limit
echo ini_get('memory_limit');        // Memory limit
echo ini_get('xdebug.max_nesting_level'); // If Xdebug is enabled

To increase recursion depth (not recommended for large values):

ini_set('max_execution_time', '300'); // Set execution time
ini_set('memory_limit', '256M');      // Increase memory limit

Conclusion

• Recursion simplifies solving problems that involve nested structures or repetitive tasks.
• Common use cases include mathematical calculations, directory traversal, and parsing JSON data.
• Performance considerations should be made, especially for functions like Fibonacci that have exponential growth.
• Always ensure proper base cases to prevent infinite recursion.

Using recursion effectively can help in writing clean and efficient PHP code for tree-based data structures, file systems, and complex computations.