Recursion vs. iteration in PHP

Question

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.

Answer 1

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.

Answer 2

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);
    }
}

Answer 3

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

Answer 4

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.