Understanding Recursion

In one of my previous articles I wrote about iterators and how you can use them. Today I’d like to look at the fraternal twin of iteration: recursion. Before we talk about recursion, though, let’s take a look at this snippet of code:

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1;	
    while ($number > 0) {
        $factorial *= $number;
        $number --;
    }
    return $factorial;
}

A factorial is the result of a number multiplied by all positive integers less than that number, and the function above calculates the factorial of any number given to it using a simple loop. Now let’s rewrite the example this way:

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number – 1);
}

We get the same results when we call both functions, but notice that the second function calculates the factorial by calling itself. This is known as recursion.

What’s Recursion?

A recursive function is one that calls itself, either directly or in a cycle of function calls. Recursion can also refer to a method of problem solving that first solves a smaller version of the problem and then uses that result plus some other computation to formulate an answer to the original problem. Often times, in the process of solving the smaller version, the method will solve yet a smaller version of the problem, and so on, until it reaches a “base case” which is trivial to solve. To write a recursive function, you need to provide it with some means of return or else it will keep calling itself for eternity (or until the call stack blows up, the script times out, or memory is exhausted). This is known as a guard clause or base case. The simplest form of a recursive function is as follows:

<?php
function my_recursive_func (args) {
    if (simplest case) {
        // The Base Case/Guard Clause that stops the
        // function from running forever
        return simple value;
    }
    else {
        //call function again with simpler args
        my_recursive_func(argsSimplified);
    }
}

Types of Recursion

When a function calls itself directly, it is referred to as direct recursion. A function in a cycle of function calls that eventually invokes itself is called indirect recursion. Look at the example below of indirect recursion:

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {	
        echo "A is Calling B($num)n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)n";
echo 'Result: ' . A($num);

Calling A(4) 
A is Calling B(3) 
B is Calling A(1) 
Result: 0

The above example is really useless code just meant to show you how a function can call itself indirectly through another function. Calling either A(n>4) or B(n>4) causes the called function to be called from the other function. It’s important to know a function can call itself indirectly like this, but in this article we’ll only deal with direct recursion.

A Practical Example

To show you how powerful recursion can be, we’ll write a function that searches for a key within an array and returns the result.

<?php
function find_in_arr($key, $arr) {
    foreach ($arr as $k => $v) {
        if ($k == $key) {
            return $v;
        }		
        if (is_array($v)) {
            foreach ($v as $_k => $_v) {
	        if ($_k == $key) {
                    return $_v;
                }
            }
        }
    }
    return false;
}

$arr = [
    'name' => 'Php Master',
    'subject' => 'Php',
    'type' => 'Articles',
    'items' => [
        'one' => 'Iteration',
        'two' => 'Recursion',
        'methods' => [
            'factorial' => 'Recursion',
            'fibonacci' => 'Recursion',
        ],
    ],
    'parent' => 'Sitepoint',
];

var_dump(
    find_in_arr('two', $arr),
    find_in_arr('parent', $arr),
    find_in_arr('fibonacci', $arr)
);

string 'Recursion' (length=9)
string 'Sitepoint' (length=9)
boolean false

Things are all well and good, but notice that we iterate only two levels deep into the array, and so the search for “Fibonacci” in the third level fails. If we want to search an array of indeterminate depth, this would not suffice. We can instead rewrite the search as a recursive function:

<?php
function find_in_arr($key, $arr) {
    foreach ($arr as $k => $v) {
        if ($k == $key) {
            return $v;
        }
        if (is_array($v)) {
            $result = find_in_arr($key, $v);
            if ($result != false) {
                return $result;
            }
        }
    }	
    return false;
}

With the recursive function, we can search an array several levels deep since we have not hardcoded how deep the function goes. It just keeps running until it goes over all of the values in the array.

Head and Tail Recursion

In all of the examples so far we’ve been using what is called head recursion. When the function calls itself, it waits for the result from the call before returning a value of its own. It is possible to write functions in such a way that they do not operate on returned values, but instead pass all required values as parameters. This is known as a tail call (or tail recursion). This method is usually preferred as a language’s runtime can sometimes optimize the calls so that there’s no danger of blowing up the call stack, but PHP does not do this. Below is our factorial example modified to make a tail call. Note that the result of the recursive call is returned, instead of manipulated further.

<?php
function factorial ($number, $factorial = 1) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero (0)');
    }
    if ($number == 0) {
        return $factorial;
    }
    else {
        return factorial($number - 1, $factorial * $number);
    }
}

General Advice

Any code that can be written iteratively can also be written recursively. However, this is not always easy to do (or even wise to do). Recursion shines when traversing trees and lists or performing most O(n log n) sorts. When you need to divide a repetitive problem up, recursion will fit better than an iterative approach, as in the case of searching within the file system and you need to enter any subdirectories to search within as well. Where there’s the traversal of an indeterminate depth, recursion works great. Keep in mind that PHP does not optimize recursive functions, even if you write them to make tail calls, and recursive functions in general are less efficient and slower than their iterative counterparts, though they sometimes do the job better as shown in the code samples above. Recursion is usually a favored alternative to iteration in functional programming and therefore most functional languages optimize recursive functions. If you’re using XDebug, be sure to inspect your system’s configuration. By default you’ll have a limit of 100 recursive calls and if you exceed this, your script will throw a “maximum nested limit reached” error. You can update the debug.max_nesting_level config value if you need to change this. Finally, it’s a good idea to read an explanation of stack heap and recursion causing stack overflow to understand what happens to the call stack during recursion.

Conclusion

In this article I’ve given you a broad look at recursion and how it compares to iteration. I’ve also show you how to write recursive functions, when to write them, and why. I have also tried warn you of some of the pitfalls that you might fall into when using recursion. Recursion is such that even many experienced programmers can go years without using it and many others have never even heard of it, which is sad because it is a truly powerful concept. I hope with this article I might have given you sufficient knowledge to go out there and start writing your own recursive functions. But remember that like with fire, you have to always be careful and use the tool wisely. Image by Alexandre Duret-Lutz via Flickr

Frequently Asked Questions (FAQs) about Understanding Recursion in PHP