PHP Recursive Function Example: Factorial Numbers
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!)
Hi Lee Davis,
At first look the non recursive function looked right to me, but then I was intrigued why you would have initialize and array with [0,1,1] elements. I understand that this is just an example of how we can optimize the overall time recursive and non recursive function take, but the example should make sense and should be testable. Any way I am sure you had a good reason for that, the main point here is for anyone else reading and comparing the performance of recursive and non recursive fibonacci : note – the $res array should contain [0,1,2] the reason fibonacci sums the previous and previous of the previous current number in your result it will not sum the last and previous elements. eg fibonacci(9) with your example will return 21 and the correct result is 34. This is how your $res[$n-1]looks:
[code]
array (size=9)
0 => int 0
1 => int 1
2 => int 1
3 => int 2
4 => int 3
5 => int 5
6 => int 8
7 => int 13
8 => int 21
[code/]
This is how it should be:
[code]
array (size=9)
0 => int 0
1 => int 1
2 => int 2
3 => int 3
4 => int 5
5 => int 8
6 => int 13
7 => int 21
8 => int 34
[code/]
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
Nice Tutorial
This is another one Factorial Program
the function coul be writtena as:
[code]
function factorial($num)
{
if($num<2)
return 1;
return $num*factorial($num-1);
}[/code]
Thanks a lot . I totally forgot about recursive function . It helped me in a project.
Nice.. I have understood very well about recursive and specially your comments helped me a lot to know more about recursive function..
Thank you
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));
Pingback: Using Methods or Functions – 12reach : php training in kolkata, wordpress training in kolkata, php jobs, interview questions
Pingback: Magento interview questions and answers for experienced | Magento Web Developer - Nikunj Vadariya
good work thanks :)
finally i learned how to use recursion, thank you