PHP中的递归与迭代

Question

迭代因子函数:

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程序中的factorial.我想通了我可以在两个方面做到这一点.

我知道这是很多问题,但因为我是PHP新手,希望有人能帮助我.

鉴于此,实际上我使用的功能不仅仅是阶乘.它还有一些其他线路可以执行其他任务.为简化起见,我们假设这些是两个函数.所以任何人都可以理解我的问题,而不是无缘无故地复杂化.

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

Answer 1

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

PHP将在我的系统上发现故障(试图找到100,000的阶乘),但迭代解决方案没有问题.但是,它们都会瞬间执行.

当然,数量小得多的阶乘INF,但这也可以应用于速度慢得多的增长函数.

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

Answer 2

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

经验法则:如果您可以迭代地编写它,请使用它.这是因为函数调用和递归在PHP中会有一些损失.此外,PHP本身并没有提供递归保护,你可能会冒着大数字内存不足的风险.

什么是行业标准？

据我所知,计算阶乘没有行业标准.一般而言,行业标准没有详细说明; 如果他们这样做,那么很棒.

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

独立于函数的真实性质,您可以通过在输入域上运行函数并对两者进行基准测试来得出关于哪个更好的结论.

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

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

也就是说,我会选择迭代解决方案.

顺便说一下,如果PHP要实现尾递归优化,你可以像这样编写阶乘函数:

function fact($n, $r = 1)
{
    if ($n < 2) {
        return $r;
    } else {
        return fact($n - 1, $r * $n);
    }
}