Wie wird Fakultät berechnet?

Question

sagen, dass es eine Funktion faktoriellen (n)

Does faktoriellen (7) schafft 7 Funktionsobjekt für jede der n 1 bis 7

zu berechnen und diese Werte verwendet werden, wenn überhaupt notwendig ist (für faktorielle (8) wie faktoriell (7) * 8)

Answer 1

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

In vielen funktionalen Sprachen (z. B. Haskell) wird garantiert, dass eine Funktion nichts ändert; nur um einen Wert zurückzugeben. Dieser Mangel an Nebenwirkungen ermöglicht es der Sprache, sich die Ergebnisse von Funktionsaufrufen zu merken/zu cachen oder zu "memoisieren".

In einer weniger anspruchsvollen Sprache könnten 7 verschiedene Funktionsaufrufrahmen auf dem Stapel platziert und entfernt werden.

Eine korrekt geschriebene Fakultät in vielen funktionalen Sprachen wäre auch tail rekursiv; In diesem Fall könnte die Sprache einfach vom unteren Ende der Funktion nach oben springen, um einen weiteren Funktionsaufruf zu vermeiden. In diesem Fall verwandelt die Sprache die rekursive Funktion in eine "freie" Schleife.

Answer 2

Es kann. Was Sie fragen, klingt wie memoization - Sie speichern frühere Ergebnisse, um Berechnungen später zu beschleunigen. Wenn Sie zum Beispiel 9! Berechnen, können Sie die Werte für 1 speichern! .. 9 !, und wenn Sie um 8 gebeten werden! später können Sie einfach den gespeicherten Wert zurückgeben. Auf ähnliche Weise können Sie, wenn Sie nach 10! Gefragt werden, 10 × 9 berechnen! schnell.

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

Eine weitere Funktion, die Memoization effektiv verwenden kann, ist das Berechnen von Fibonacci-Zahlen.

Answer 3

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

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

Diese Funktion aufrufen selbst recursively die Anzahl der Zeiten erforderlich, um die gegebenen faktorielles (n) zu berechnen.

Meistens alle rekursiven Funktionen können durch die Verwendung eines Stapels in eine iterative Lösung umgewandelt werden, um die aufeinander folgenden Ergebnisse zu akkumulieren ...

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