Wie wird faktorielles berechnet?

Question

sagen, es ist eine Funktion factorial berechnen (n)

Enthält faktoriell (7) schafft 7 Funktionsobjekt für jede der n 1 bis 7

und diese Werte verwenden, wann immer notwendig (für factorial (8) als wie faktorielle (7) * 8)

Answer 1

Es hängt von der Sprache und der Sprache Umsetzung.

In vielen funktionalen Sprachen (zum Beispiel Haskell) wird eine Funktion garantiert nichts ändern; nur einen Wert zurückgeben. Dieser Mangel an Nebenwirkungen ermöglicht die Sprache / Cache zu erinnern, oder „memoize“, die Ergebnisse der Funktionsaufrufe.

In einer weniger anspruchsvollen Sprache, 7 verschiedene Funktionsaufruf Rahmen auf den Stapel gelegt werden könnten, und tauchte ab.

Eine richtig geschrieben Fakultäts-Funktion in vielen funktionalen Sprachen wäre auch Schwanz rekursive; in diesem Fall könnte wählen, die Sprache einfach aus dem Boden der Funktion nach oben einem weiteren Funktionsaufruf zu vermeiden, springen zu schaffen. In diesem Fall dreht sich die Sprache der rekursiven Funktion in einer Schleife „kostenlos“.

Answer 2

Es hängt davon ab, klingt wie Sie eine rekursive Fakultäts-Funktion sprechen:

int factorial(int n) {
    return n>=1 ? n * factorial(n-1) : 1;
}

Diese Funktion wird selbst aufrufen rekursiv die Anzahl der zur Berechnung benötigt die gegeben faktorielles (n).

Meistens alle rekursiven Funktionen können mit einem Stapel akkumulieren die aufeinander folgenden Ergebnisse in eine iterative Lösung umgewandelt werden ...

int factorial(int n) {
    int accu = 1;
    int i;
    for(i = 1; i <= n; i++) {
        accu *= i;
    }
    return accu;
}

Answer 3

Es kann. Was Sie fragen, klingt wie memoization - Sie frühere Ergebnisse speichern spätere Berechnungen zu beschleunigen. So zum Beispiel, wenn Sie 9 berechnen !, können Sie die Werte für 1 speichern! .. 9 !, und wenn Sie für 8 gefragt werden! später können Sie nur den gespeicherten Wert zurück. wenn gefragt Ebenso für 10 !, können Sie 10 × 9 berechnen! schnell.

Die Sache ist die, dass Fakultäts ( n ) wächst so schnell, für große Werte von n können Sie eine Menge Speicherplatz am Ende mit, so dass die Raum-Zeit-Handel kann nicht sinnvoll sein.

Eine weitere Funktion, die memoization effektiv nutzen kann, ist die Berechnung Fibonacci-Zahlen.