Factorial

Q: Wie hoch ist die Zeitkomplexität der Berechnung einer Fakultät?

Sowohl die Schleife als auch die Rekursion führen für jede Zahl bis n eine Multiplikation aus, daher beträgt die Laufzeit O(n) . Die Schleife benötigt zusätzlichen Speicherplatz von O(1) . Die Rekursion behält bis zur Rückkehr aus dem Basisfall für jeden Aufruf einen Stackframe bei und benötigt daher O(n) Speicherplatz.

Q: Warum ist 0! gleich 1?

0! ist das Produkt aus keiner Zahl, und ein Produkt ohne Faktoren ist 1 , genauso wie eine Summe ohne Summanden 0 ist. So bleibt auch die Regel n! = n × (n-1)! für n = 1 wahr: 1! = 1 × 0! = 1 . Auch das Abzählen stimmt damit überein: Es gibt genau eine Möglichkeit, null Elemente anzuordnen.

Q: Ist Rekursion oder eine Schleife besser für die Fakultät?

Sie führen dieselben Multiplikationen aus und liefern dasselbe Ergebnis. Die rekursive Version liest sich wie die mathematische Definition, weshalb sie eine klassische erste Übung zur Rekursion ist. Die Schleife benötigt konstanten Speicher und kann keinen Stacküberlauf verursachen, daher ist sie in echtem Code die bessere Wahl.

EinsteigerMathe und Simulation Rekursion

+10

Die Fakultät einer ganzen Zahl n, geschrieben n!, ist das Produkt aller ganzen Zahlen von 1 bis n. Zum Beispiel: 4! = 1 × 2 × 3 × 4 = 24. Per Definition gilt 0! = 1. Deine Funktion erhält n und gibt n! zurück.

Funktion

factorial(n: integer) → integer

ninteger: die ganze Zahl, deren Fakultät du berechnest
Gibt zurückinteger: das Produkt aller ganzen Zahlen von 1 bis n, das 1 ist, wenn n gleich 0 ist

Einschränkungen

0 ≤ n ≤ 12
Die Antwort passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl: Die größte ist 12! = 479001600.

Beispiele

Eingabe: n = 5
Ausgabe: 120
Erklärung: Multipliziere 1 × 2 × 3 × 4 × 5. Das laufende Produkt ergibt 1, 2, 6, 24 und endet bei 120.

Eingabe: n = 0
Ausgabe: 1
Erklärung: Es gibt nichts zu multiplizieren, und ein Produkt ohne Faktoren ist 1. Deshalb gilt 0! = 1.

Weiterführende Frage

100! hat 158 Ziffern. Kannst du zählen, wie viele Nullen am Ende stehen, ohne es auszurechnen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Fakultät hat zwei gleichwertige Beschreibungen, und aus jeder lässt sich Code machen. Als Produkt gilt n! = 1 × 2 × ... × n, was einer Schleife entspricht. Als rekursive Definition gilt 0! = 1 und n! = n × (n-1)!, was einer Funktion entspricht, die sich selbst aufruft. Beide führen etwa n Multiplikationen aus. Die Schleife ist die Variante, mit der wir abschließen, denn sie benötigt keinen Aufrufstapel.

Rekursion aus der Definition

Idee

Die Fakultät ist über eine kleinere Fakultät definiert: n! = n × (n-1)!. Wenn du bereits 4! = 24 kennst, dann gilt 5! = 5 × 24 = 120. Eine rekursive Funktion schreibt diesen Satz als Code. Um factorial(n) zu berechnen, fragt sie nach factorial(n-1) und multipliziert das Ergebnis mit n.

Die Aufrufe brauchen eine Stelle, an der sie enden: den Basisfall. factorial(0) gibt 1 zurück, ohne etwas aufzurufen. Jeder Aufruf verringert n um eins, daher gehen die Aufrufe von 5 aus über 5, 4, 3, 2, 1, 0. Dann kommen die Ergebnisse die Kette wieder hinauf zurück: 1, 1, 2, 6, 24, 120.

Es gibt n + 1 Aufrufe und n Multiplikationen, also beträgt die Laufzeit O(n). Jeder Aufruf wartet auf dem Stack, bis der darunterliegende Aufruf zurückkehrt. Daher enthält der Stack n + 1 Frames, was einem Speicherbedarf von O(n) entspricht. Bei n ≤ 12 ist das winzig, aber dasselbe Muster führt bei einer großen Eingabe zu einem Stackoverflow.

Algorithmus

Wenn n 0 ist, gib 1 zurück. Dies ist der Basisfall.
Andernfalls ruf die Funktion mit n-1 auf.
Multipliziere dieses Ergebnis mit n und gib es zurück.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

In einer Schleife multiplizieren

Idee

Rolle die Rekursion auf, und du erhältst ein laufendes Produkt. Beginne mit result = 1 und multipliziere es mit 2, dann mit 3 und so weiter bis hin zu n. Für n = 5 entwickelt sich das Ergebnis zu 1, 2, 6, 24, 120.

Der Start bei 1 deckt auch die kleinsten Eingaben ab. Für n = 0 und n = 1 wird die Schleife von 2 bis n kein einziges Mal ausgeführt, und die Funktion gibt den Startwert 1 zurück, was in beiden Fällen die richtige Antwort ist.

Die Schleife führt n-1 Multiplikationen aus, benötigt O(n) Zeit und speichert eine Zahl, also O(1) Speicherplatz. Es gibt keinen Aufrufstapel, der überlaufen könnte. Deshalb erwarten Interviewer diese Version, nachdem du die rekursive Version gezeigt hast.

Algorithmus

Setze result = 1.
Durchlaufe k von 2 bis n, einschließlich beider Werte.
Multipliziere result bei jedem Schritt mit k.
Gib result zurück.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Stolperfallen und Grenzfälle

Der Code für die Fakultät ist kurz, daher stecken die Fehler in den Randfällen.

Das Produkt bei 0 beginnen lassen. Bei jeder Multiplikation bleibt es 0. Der Startwert eines Produkts ist 1.
Die Rekursion nur bei n == 1 beenden. Wird die Funktion mit 0 aufgerufen, erreicht sie nie ihren Basisfall: Sie läuft weiter bis -1, -2 und so weiter, bis der Stapel überläuft. Mach n == 0 zum Basisfall.
Mit k < n statt mit k ≤ n iterieren. Dadurch fehlt der letzte Faktor und es wird (n-1)! zurückgegeben, sodass 5 24 statt 120 ergibt.
Überläufe ignorieren. 13! = 6227020800 passt nicht in eine vorzeichenbehaftete 32-Bit-Ganzzahl. In Java und C# wird das Produkt stillschweigend zu einer falschen Zahl umgebrochen, in C ist ein vorzeichenbehafteter Überlauf ein undefiniertes Verhalten, und ein Rust-Debug-Build löst eine Panic aus. Eine 64-Bit-Ganzzahl reicht bis 20!; darüber hinaus brauchst du Big Integers.
In Swift for k in 2...n schreiben. Ein geschlossener Wertebereich, dessen Ende kleiner als sein Anfang ist, führt zur Laufzeit zu einem Absturz, wenn n 0 oder 1 ist.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität der Berechnung einer Fakultät?

Sowohl die Schleife als auch die Rekursion führen für jede Zahl bis n eine Multiplikation aus, daher beträgt die Laufzeit O(n). Die Schleife benötigt zusätzlichen Speicherplatz von O(1). Die Rekursion behält bis zur Rückkehr aus dem Basisfall für jeden Aufruf einen Stackframe bei und benötigt daher O(n) Speicherplatz.

Warum ist 0! gleich 1?

0! ist das Produkt aus keiner Zahl, und ein Produkt ohne Faktoren ist 1, genauso wie eine Summe ohne Summanden 0 ist. So bleibt auch die Regel n! = n × (n-1)! für n = 1 wahr: 1! = 1 × 0! = 1. Auch das Abzählen stimmt damit überein: Es gibt genau eine Möglichkeit, null Elemente anzuordnen.

Ist Rekursion oder eine Schleife besser für die Fakultät?

Sie führen dieselben Multiplikationen aus und liefern dasselbe Ergebnis. Die rekursive Version liest sich wie die mathematische Definition, weshalb sie eine klassische erste Übung zur Rekursion ist. Die Schleife benötigt konstanten Speicher und kann keinen Stacküberlauf verursachen, daher ist sie in echtem Code die bessere Wahl.

def factorial(n):
    # Schreibe hier den Code

Test #1

Test #2

Argument

n = 5

Erwartete Ausgabe