Рекурсия против итерации в 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));
    }
}

Мне нужно разработать функцию для вычисления factorial в моей PHP-программе. Я понял, что могу сделать это в обоих направлениях.

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

Я знаю, что у меня много вопросов, но поскольку я новичок в PHP и надеюсь, что кто-то поможет мне.

Учитывая, что фактически функция, которую я использую, не просто факторная. У него есть и другие линии, которые выполняют некоторые другие задачи. Для упрощения предположим, что это две функции. Так что любой может понять мой вопрос, а не скомпоновать его без причины.

В основном я имею в виду рекурсию против итерации в PHP.

Ответ 1

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

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

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

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

Ответ 2

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

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

Какой промышленный стандарт?

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

Как выбрать один из методов между двумя?

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

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

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

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

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

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

Ответ 3

Как мне известно, первая лучше, чем рекурсия. Потому что это вызывает много накладных расходов для системы и иногда останавливает script.

Ответ 4

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

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