26

Iterative factorial function:

function factorial($number) {
    $result = 1;
    while ($number > 0) {
        $result *= $number;
        $number--;
    }
    return $result;
}

Recursive factorial function:

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

I have to develop a function to calculate factorial in my PHP program. I figured it out that I could do it in above both ways.

  • What I don't know is which method is better to used and why?
  • What's the industry standard?
  • How can I select one of the methods between above two?
  • What's the condition to determine which one is better?

I know It's a lot of questions but since I'm new to PHP and hope someone will help me out.

Given that, actually the function I'm using is not just factorial. It has got some other lines too which do some other tasks. For the sake of simplification let's assume that these are the two functions. So anyone can understand my question rather complexing it for no reason.

What I'm basically referring to is the recursion vs. iteration in PHP.

hakre
  • 193,403
  • 52
  • 435
  • 836
Techie
  • 44,706
  • 42
  • 157
  • 243
  • 5
    When in doubt, don't use recursion in PHP :) – Ja͢ck Oct 10 '12 at 02:09
  • 2
    If you see the comment in http://stackoverflow.com/questions/6171807/does-php-optimize-tail-recursion you should have your answer. – Suroot Oct 10 '12 at 02:10
  • 2
    There is no "standard." Some programs can be much more elegantly written in recursive form. Some can't. The one downside of recursion is that it generates a stack frame for each function call. Get enough of those, and you get a stack overflow. – NullUserException Oct 10 '12 at 02:12
  • 1
    industry standard would usually use built in functions. gmp_fact(n) – Nick Maroulis Oct 10 '12 at 02:23
  • @Dasum: Which specific PHP 5 version is this question related to? – hakre Oct 10 '12 at 02:37
  • @hakre I thought PHP5 supports recursion and iteration. – Techie Oct 10 '12 at 02:52
  • Thanks for the link and the information – Techie Oct 10 '12 at 02:54
  • @Dasun: As long as you're generally asking about the PHP programming language, just tag it PHP. If you are concerned about a specific differentiation in some version, add the version number to the tag, like PHP-5.1. – hakre Oct 10 '12 at 02:56
  • I wrote an additional detail here https://stackoverflow.com/questions/660337/recursion-vs-loops/55509199#55509199 – Danyal Sandeelo Apr 04 '19 at 06:30

4 Answers4

21

Php is a special case. You will use less memory using the iterative solution. Moreover, function calls in PHP are costly, so it's better to avoid function calls when you can.

PHP will seg fault (on my system) trying to find the factorial of 100,000, but the iterative solution has no problems. Both of them execute practically instantaneously, though.

Of course, factorial of a much smaller number is INF, but this could also be applied to a much slower growing function.

If we're not talking about PHP or another scripting langauge, then there is no standard. It's good to know how to do it both ways. I would go with whichever leads to the cleanest code.

Explosion Pills
  • 188,624
  • 52
  • 326
  • 405
  • 1
    This is no longer accurate. If you run a recursive factorial function of a value like 100000, it completes. I think this is because PHP now uses [trampolines](http://blog.jpauli.tech/2016-09-16-php-7-magic-function-call-trampoline-html/)? See online [runnable example](https://3v4l.org/FVDot#v8.2.2). – mbomb007 Feb 06 '23 at 17:21
11

What I don't know is which method is better to used and why?

Rule of thumb: If you can write it iteratively, use that. This is because function calls and recursion come with some penalty in PHP. Also, PHP doesn't natively come with recursion protection and you'd risk running out of memory on big numbers.

What's the industry standard?

As far as I know, there's no industry standard for calculating a factorial. In general, industry standards don't go into such detail; if they do, then great.

How can I select one of the methods between above two?

Independent of the true nature of your functions, you can reach a conclusion as to which is better by yourself as well, simply by running the functions over the input domain and benchmarking both.

What's the condition to determine which one is better?

Memory and time are important factors. You should try to achieve low memory consumption AND short execution time. This is not always possible, in which case you need to compromise either one.

That said, I would opt for an iterative solution.

Btw, if PHP were to ever implement tail recursion optimization, you could write the factorial function like so:

function fact($n, $r = 1)
{
    if ($n < 2) {
        return $r;
    } else {
        return fact($n - 1, $r * $n);
    }
}
Ja͢ck
  • 170,779
  • 38
  • 263
  • 309
2

As per my knowledge the first one is better than recursion. Because it causes lots of overhead to system and sometimes stop the script.

George Stocker
  • 57,289
  • 29
  • 176
  • 237
Yogesh Suthar
  • 30,424
  • 18
  • 72
  • 100
1

I created a script to test which of these methods is faster.

$f = 12; //calculate factorial of this number
$n = 10000000; //the number of times the process is repeated

//factorial using iterative function
function f1($a) {
    $r = $a;
    for($i=$a-1; $i >= 2; $i--)
        $r *= $i;
    return $r;
}

//factorial using recursive function
function f2($a) {
    return $a < 2 ? 1 : $a * f2($a - 1);
}

echo "\n\n";

$start = microtime(true);
for($i=0; $i < $n; $i++)
    $x = f1($f);
echo "f1(): " . ((microtime(true) - $start) * 1000) . " ms\n";

$start = microtime(true);
for($i=0; $i < $n; $i++)
    $x = f2($f);
echo "f2(): " . ((microtime(true) - $start) * 1000) . " ms\n";

Results:

f1():  6 648 ms
f2(): 12 415 ms

Besides the fact that the recursion uses more memory, it's approximately 1.87 times slower than the iteration. Tested on PHP 7.

Genhis
  • 1,484
  • 3
  • 27
  • 29