Rekursion vs. Iteration in PHP

Iterative Fakultätsfunktion:

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

Rekursive Fakultätsfunktion:

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

Ich muss eine Funktion entwickeln, um die Fakultät in meinem PHP-Programm zu berechnen. Ich habe herausgefunden, dass ich es auf beide Arten machen kann.

• Was ich nicht weiß, ist, welche Methode besser zu verwenden ist und warum?
• Was ist der Industriestandard?
• Wie kann ich eine der oben genannten Methoden auswählen?
• Was ist die Bedingung, um festzustellen, welches besser ist?

Ich weiß, es sind viele Fragen, aber da ich neu in PHP bin und hoffe, dass mir jemand helfen wird.

Angesichts dessen ist die Funktion, die ich verwende, nicht nur Fakultät. Es hat auch einige andere Linien, die andere Aufgaben erledigen. Nehmen wir der Einfachheit halber an, dass dies die beiden Funktionen sind. Jeder kann also meine Frage verstehen, anstatt sie ohne Grund zu komplexieren.

Worauf ich mich im Grunde beziehe, ist die Rekursion vs. Iteration in PHP.

PHP ist ein Sonderfall. Mit der iterativen Lösung benötigen Sie weniger Speicher. Darüber hinaus sind Funktionsaufrufe in PHP kostspielig, daher ist es besser, Funktionsaufrufe zu vermeiden, wenn Sie können.

PHP wird (auf meinem System) versuchen, die Fakultät von 100.000 zu finden, aber die iterative Lösung hat keine Probleme. Beide werden jedoch praktisch augenblicklich ausgeführt.

Fakultät einer viel kleineren Zahl ist natürlich INFaber dies könnte auch auf eine viel langsamer wachsende Funktion angewendet werden.

Wenn wir nicht über PHP oder eine andere Skriptsprache sprechen, dann gibt es keinen Standard. Es ist gut zu wissen, wie es in beide Richtungen geht. Ich würde mit dem gehen, was zum saubersten Code führt.

Was ich nicht weiß, ist, welche Methode besser zu verwenden ist und warum?

Faustregel: Wenn Sie es iterativ schreiben können, verwenden Sie das. Dies liegt daran, dass Funktionsaufrufe und Rekursion in PHP mit einigen Nachteilen verbunden sind. Außerdem verfügt PHP nicht nativ über einen Rekursionsschutz, und Sie riskieren, dass Ihnen bei großen Zahlen der Speicher ausgeht.

Was ist der Industriestandard?

Soweit ich weiß, gibt es keinen Industriestandard für die Berechnung einer Fakultät. Im Allgemeinen gehen Industriestandards nicht so ins Detail; wenn sie es tun, dann großartig.

Wie kann ich eine der oben genannten Methoden auswählen?

Unabhängig von der wahren Natur Ihrer Funktionen können Sie auch selbst zu einer Schlussfolgerung kommen, welche besser ist, indem Sie einfach die Funktionen über die Eingabedomäne laufen lassen und beide Benchmarks durchführen.

Was ist die Bedingung, um festzustellen, welches besser ist?

Gedächtnis und Zeit sind wichtige Faktoren. Sie sollten versuchen, einen geringen Speicherverbrauch UND eine kurze Ausführungszeit zu erreichen. Dies ist nicht immer möglich, in diesem Fall müssen Sie einen Kompromiss eingehen.

Allerdings würde ich mich für eine iterative Lösung entscheiden.

Übrigens, wenn PHP jemals eine Schwanzrekursionsoptimierung implementieren würde, könnten Sie die Fakultätsfunktion so schreiben:

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

Nach meinem Wissen ist der erste besser als Rekursion. Weil es viel Overhead für das System verursacht und manchmal das Skript stoppt.

Ich habe ein Skript erstellt, um zu testen, welche dieser Methoden schneller ist.

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

Ergebnisse:

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

Abgesehen davon, dass die Rekursion mehr Speicher benötigt, ist sie ungefähr 1,87-mal langsamer als die Iteration. Getestet auf PHP 7.