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.

If you see the comment in stackoverflow.com/questions/6171807/… you should have your answer. — Suroot
– Suroot, Commented Oct 10, 2012 at 2:10
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
– NullUserException, Commented Oct 10, 2012 at 2:12
industry standard would usually use built in functions. gmp_fact(n) — Nick Maroulis
– Nick Maroulis, Commented Oct 10, 2012 at 2:23
@Dasum: Which specific PHP 5 version is this question related to? — hakre
– hakre, Commented Oct 10, 2012 at 2:37

Explosion Pills · Accepted Answer · 2013-05-30 14:35:58Z

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.

edited May 30, 2013 at 14:35

answered Oct 10, 2012 at 2:22

Explosion Pills

192k56 gold badges341 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

mbomb007 Over a year ago

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? See online runnable example.

Ja͢ck · Accepted Answer · 2012-10-10 02:45:35Z

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

edited Oct 10, 2012 at 2:45

answered Oct 10, 2012 at 2:11

Ja͢ck

174k39 gold badges269 silver badges316 bronze badges

2 Comments

Ja͢ck Over a year ago

@NullUserException There is, the recursion is the last statement of the function, so it would be safe to replace the stack.

NullUserException Over a year ago

And you magically multiply $number by the result of the recursive call before it has executed?

George Stocker · Accepted Answer · 2012-10-10 02:25:18Z

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.

edited Oct 10, 2012 at 2:25

George Stocker

58k29 gold badges184 silver badges239 bronze badges

answered Oct 10, 2012 at 2:13

Yogesh Suthar

30.5k18 gold badges75 silver badges100 bronze badges

Comments

Genhis · Accepted Answer · 2019-09-15 11:27:07Z

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.

Collectives™ on Stack Overflow

Recursion vs. iteration in PHP

4 Answers 4

1 Comment

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related