Recursive functions

Sometimes the easiest way to model a problem is to make a function call itself - a technique known as recursive function calling. Calculating factorials is a commonly cited example - the factorial of 6 is 6 * 5 * 4 * 3 * 2 * 1, or 720, and is usually represented as 6! So, given that factorial 6 (6!) is 720, what is factorial 7, and how does it relate to 6!? Well, clearly 7! is 7 * 6! - once you calculate 6!, it is simply a matter of multiplying the result by 7 to get 7!

This equation can be represented like this: n! = n * ((n - 1)!) That is, the factorial for any given number is equal to that number multiplied by the factorial of the number one lower - this is clearly a case for recursive functions!

So, what we need is a function that will accept an integer, and, if that integer is not 0, will call the function again, this time passing in the same number it accepted minus 1, then multiply that result by itself. If it is sounding hard, then you are in for a surprise: the function to calculate factorials is made up of only two lines of code. Here is a working script to calculate factorials:

<?php
    function factorial($number) {
        if ($number == 0) return 1;
        return $number * factorial($number - 1);
    }

    print factorial(6);
?>

That will output 720, although you can easily edit the factorial() function call to pass in 20 rather than 6, for example. Note that factorials increase in value very quickly (7! is 5040, 8! is 40320, etc), and so you will eventually hit a processing limit - not time, but merely recursive complexity; PHP will only allow you to have a certain level of recursion (about 18000! is about the max you are likely to be able to calculate using the above code).

As you can see, recursive functions make programming certain tasks particularly easy, and it is not all algorithms, either - consider how easy it is to write a function showchildren() for a forum, which automatically shows all replies to a message, and all replies to those replies, and all replies to the replies to the replies, etc.

Copyright ©2015 Paul Hudson. Follow me: @twostraws.