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!
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 :)
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
You can still use it, anyone who read this and knows the answer is worth employing, surely? ;)
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!)
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
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.
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?
Be my guest - post the link here if you do write that?
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
Does php implement tail call optimizaion?
How big a $number can be provided before you run into numeric troubles (if any)? And how big before the stack blows (if ever)?
BTW, some nice reading on Factorials and related subjects: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
This is good example
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