25

迭代阶乘函数：

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

递归阶乘函数：

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

我必须开发一个函数来计算我的 PHP 程序中的阶乘。我发现我可以通过以上两种方式做到这一点。

  • 我不知道哪种方法更好用，为什么？
  • 行业标准是什么？
  • 如何在上述两种方法中选择一种？
  • 确定哪个更好的条件是什么？

我知道这是很多问题，但由于我是 PHP 新手，希望有人能帮助我。

鉴于此，实际上我使用的函数不仅仅是阶乘。它也有一些其他的行来完成一些其他的任务。为了简化起见，我们假设这是两个函数。所以任何人都可以理解我的问题，而不是无缘无故地把它复杂化。

我基本上指的是 PHP 中的递归与迭代。

4

4 回答 4

21

PHP 是一个特例。使用迭代解决方案将使用更少的内存。此外，PHP 中的函数调用成本很高，因此最好尽可能避免函数调用。

PHP 将 seg fault（在我的系统上）试图找到 100,000 的阶乘，但迭代解决方案没有问题。不过，它们几乎都是即时执行的。

当然，小得多的阶乘是INF，但这也可以应用于增长慢得多的函数。

如果我们不是在谈论 PHP 或其他脚本语言，那么就没有标准。很高兴知道如何以两种方式做到这一点。我会选择最干净的代码。

于 2012-10-10T02:22:16.167 回答
11

我不知道哪种方法更好用，为什么？

经验法则：如果您可以迭代地编写它，请使用它。这是因为函数调用和递归在 PHP 中会带来一些损失。此外，PHP 本身并没有递归保护，您可能会冒着在大数字上耗尽内存的风险。

行业标准是什么？

据我所知，计算阶乘没有行业标准。一般来说，行业标准不会详细说明；如果他们这样做，那就太好了。

如何在上述两种方法中选择一种？

独立于函数的真实性质，您也可以通过在输入域上运行函数并对两者进行基准测试来得出自己更好的结论。

确定哪个更好的条件是什么？

记忆和时间是重要的因素。您应该尝试实现低内存消耗和短执行时间。这并不总是可能的，在这种情况下，您需要妥协其中任何一个。

也就是说，我会选择迭代解决方案。

顺便说一句，如果 PHP 要实现尾递归优化，您可以像这样编写阶乘函数：

function fact($n, $r = 1)
{
    if ($n < 2) {
        return $r;
    } else {
        return fact($n - 1, $r * $n);
    }
}
于 2012-10-10T02:11:19.863 回答
2

据我所知，第一个比递归更好。因为它会给系统带来很多开销，有时还会停止脚本。

于 2012-10-10T02:13:33.747 回答
1

我创建了一个脚本来测试哪些方法更快。

$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";

结果：

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

除了递归使用更多内存这一事实之外，它比迭代慢了大约 1.87 倍。在 PHP 7 上测试。

于 2016-12-15T16:29:58.500 回答