PHP Recursive Function Example: Factorial Numbers

I spun up the simplest example I could think of to illustrate a recursive function to a PHP beginner the other day, and I thought I'd share. I often don't post really basic content but I should - people are beginning to be beginners all the time, after all!

Factorials

Factorials are a very easy maths concept. They are written like 5! and this means 5 * 4 * 3 * 2 * 1. So 6! is 720 and 4! is 24.

6! is the same as 6 * 5!, or 6 * 5 * 4! ... and this is where the recursive functions come in.

Recursive Functions

We're going to do the same thing, over and over, using the output of the previous function call to inform what to pass into the next function call - so we need a recursive function! Here's my code snippet for calculating factorials:

function factorial($number) { 
 
    if ($number < 2) { 
        return 1; 
    } else { 
        return ($number * factorial($number-1)); 
    } 
}

You can call factorial(6) for example, and it will first of all figure out that it should jump into the else clause. However this causes a call to factorial so PHP will go to work that out and realise that it needs to call the function again ... and so on. When ($number - 1) eventually gets small enough, we'll return a 1 rather than calling the function again, and each of the nested function calls will find its return value and return. When we get to the top of the call stack, we've got the answer!

I personally really like recursive functions for operations like this, calculating the fibonacci series is also a nice example, and I also use an approach like this for processing potentially-nested data in arrays for example. So if the value of the next element is an array, pass the whole thing into a recursive call to this function, otherwise do whatever you were going to do ... sometimes the simplest solutions are the best!

21 thoughts on “PHP Recursive Function Example: Factorial Numbers

  1. It's actually shaking my head of old memories :) Every programmers should have some base of algorithm. So factorial is the easiest, the best and used ever for recursive :)

  2. Aww... now I can't use this as a quick test when interviewing people :)

    It tripped up quite a few people too :)

    As for the article, it is well written and informative as always.
    Thank you for sharing.

    Cheers,
    Peter

  3. Great example. I find recursive functions mostly useful for processing data sets with an unknown number of dimensions.

    As for calculating the Fibonacci series using recursive functions, I think using straight loops would be a more elegant solution. Take the following recursive function for example..

    function fibonacci ($n)
    {
    if ($n == 1 || $n == 2)
    {
    return 1;
    }
    else
    {
    return fibonacci($n - 1) + fibonacci($n - 2);
    }
    }

    To find the 10th number in the Fibonacci sequence using this recursive function would take 109 iterations. However to find the same value using a straight while loop can be done in a measly 7.

    function fibonacci($n)
    {
    $res = array(0, 1, 1);
    if (isset($res[$n-1]))
    {
    return $res[$n-1];
    } else
    {
    while (($a = sizeof($res)) < $n)
    {
    $res[] = $res[$a-1] + $res[$a-2];
    }
    }
    return $res[$n-1];
    }

    • actually one of Zend's training courses has an exercise which asks you to do the fibonacci sequence both as a loop and then as a recursive function. It's quite fun (and I get to talk about max_execution_time too, every time!)

  4. I have always found it slightly strange that the examples used to illustrate recursion are very often infinite sequences. Since you are going to execute a repeated calculation a known number of times (otherwise you can go forever) you can use a for loop much more readably e.g.
    [code]
    function factorial($number) {
    $factorial = $number--;
    for ($i = $number; $i > 0; $i--) {
    $factorial = $i * $factorial;
    }
    return $factorial;
    }
    [/code]
    In my opinion recursion only makes sense for nested structures where you don't know the depth in advance then they can be quite elegant. Despite being confusing to debug they are often great fun to play with. There are some interesting points here http://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursion_versus_iteration

  5. If this is something you are going to do repeatedly it may be worthwhile storing the result of each recursion for use later:

    [code]
    facts = array();
    }

    public function factorial($number) {
    return $this->calculateFactorial($number);
    }

    private function calculateFactorial($number) {
    if($number facts)) {
    return $this->facts[$number];
    } else {
    $calculatedFactorial = ($number * $this->calculateFactorial($number-1));
    $this->facts[$number] = $calculatedFactorial;
    return ($calculatedFactorial);
    }
    }
    }
    }

    $f = new Factorial();
    echo $f->factorial(4);
    echo $f->factorial(6);
    echo $f->factorial(25);
    echo $f->factorial(7);
    [/code]

    This means if you already calculated any factorials for $number or less then you don't have to calculate them all again.

  6. A nice tidbit of information about recursion and php usage is that the stack is not infinite. So if you have xdebug enabled, you might have trouble calculating fib(33), and even without it, you might hit the limit sooner than you think.
    Some considerations about the speed and memory consumption of a recursive implementation vs. a or loop-based one would also be welcome. In a followup blogpost maybe?

  7. Surprised there's no mention of tail-recursive optimization:
    function fact($n, $total=1) {
    if($n < 2)
    return $total;
    else
    return fact($n-1, $total * $n);
    }
    By passing a running total we can save the space and time required as well as avoiding worry about the stack size. Cheers!
    https://en.wikipedia.org/wiki/Tail_call

  8. Hey Lorna,

    thanks for the re-introduction to these. It sure has been ages and I've spent about 2 hours getting back up to speed on them. But they sure helped me convert a nested array into an XML string with SimpleXMLElement. Well, quicker and simpler than it likely would have been. Many thanks for the inspiration.

    Matt

  9. the function coul be writtena as:
    [code]
    function factorial($num)
    {
    if($num<2)
    return 1;
    return $num*factorial($num-1);
    }[/code]

  10. Nice.. I have understood very well about recursive and specially your comments helped me a lot to know more about recursive function..

    Thank you

  11. This is a good example, one thing I'm wondering is why you return
    return ($number * factorial($number-1));
    instead of just
    return (factorial($number-1));

  12. Pingback: Using Methods or Functions – 12reach : php training in kolkata, wordpress training in kolkata, php jobs, interview questions

  13. Pingback: Magento interview questions and answers for experienced | Magento Web Developer - Nikunj Vadariya

Leave a Reply

Please use [code] and [/code] around any source code you wish to share.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>