Рекурсия против итерации в PHP

Итеративная факторная функция:

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.

 23
phploops
Author: hakre, 2012-10-10
Source

4 answers

Php - это особый случай. Вы будете использовать меньше памяти, используя итеративное решение. Кроме того, вызовы функций в PHP являются дорогостоящими, поэтому лучше избегать вызовов функций, когда это возможно.

PHP обнаружит ошибку (в моей системе), пытаясь найти факториал 100 000, но итеративное решение не имеет проблем. Однако оба они выполняются практически мгновенно.

Конечно, факториал гораздо меньшего числа равен INF, но это также может быть применено к гораздо более медленному растущая функция.

Если мы не говорим о PHP или другом языке сценариев, то стандарта не существует. Хорошо знать, как это сделать в обоих направлениях. Я бы выбрал то, что приведет к самому чистому коду.

 19
Author: Explosion Pills, 2013-05-30 14:35:58

Чего я не знаю, так это какой метод лучше использовать и почему?

Эмпирическое правило: Если вы можете написать его итеративно, используйте это. Это связано с тем, что вызовы функций и рекурсия в PHP сопряжены с некоторым штрафом. Кроме того, PHP изначально не поставляется с защитой от рекурсии, и вы рискуете исчерпать память на больших числах.

Каков отраслевой стандарт?

Насколько я знаю, нет отраслевого стандарта для вычисления факториала. В общем, отраслевые стандарты не вдаются в такие детали; если они это делают, то отлично.

Как я могу выбрать один из методов между двумя вышеперечисленными?

Независимо от истинной природы ваших функций, вы также можете прийти к выводу о том, что лучше самостоятельно, просто запустив функции во входной области и сравнив их.

При каких условиях можно определить, какой из них лучше?

Память и время являются важными факторами. Вы должны постарайтесь добиться низкого потребления памяти И короткого времени выполнения. Это не всегда возможно, и в этом случае вам нужно пойти на компромисс с любым из них.

Тем не менее, я бы выбрал итеративное решение.

Кстати, если бы PHP когда-либо реализовал оптимизацию хвостовой рекурсии, вы могли бы написать факториальную функцию следующим образом:

function fact($n, $r = 1)
{
    if ($n < 2) {
        return $r;
    } else {
        return fact($n - 1, $r * $n);
    }
}
 11
Author: Ja͢ck, 2012-10-10 02:45:35

Насколько мне известно, первый вариант лучше, чем рекурсия. Потому что это приводит к большим затратам на систему и иногда останавливает сценарий.

 2
Author: Yogesh Suthar, 2012-10-10 02:25:18

Я создал скрипт, чтобы проверить, какой из этих методов быстрее.

$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.

 0
Author: Genhis, 2016-12-15 16:29:58