Rekursive Fakultät

Für positive Werte von $n$n, bedeutet $n!$n, !, wie bereits gesehen, ein Produkt von Zahlen von $n$n bis 1: Also $n!$n, ! = $n\cdot (n-1) \cdots 2 \cdot 1$n, dot, left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1. . Dabei ist $(n-1) \cdots 2 \cdot 1$left parenthesis, n, minus, 1, right parenthesis, \@cdots, 2, dot, 1 eine andere Schreibweise für $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !, Und so können wir sehen, dass $n! = n \cdot (n-1)!$n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! ist. Hast du gemerkt, was wir gerade gemacht haben? Wir haben $n$n geschrieben als ein Produkt, in dem einer der Faktoren $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, ! ist. _Du kannst $n!$n, ! berechnen indem du $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, ! berechnest und dann das Ergebnis von $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, ! mit $n$n multiplizierst.Du kannst die Fakultät von $n$n berechnen, indem du zuerst die Fakultät von $n-1$n, minus, 1 berechnest. Wir sagen, dass die Berechnung von $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, ! ein Subproblem ist, das wir lösen müssen, um $n$n zu berechnen!

Als Beispiel berechnen wir 5!.

So jetzt haben wir einen anderen Weg gefunden, den Wert von $n!$n, !, für alle natürlichen Zahlen $n$n zu bestimmen:

Wenn wir $n!$n, ! auf diese Weise berechnen nennen wir den ersten Fall, wo wir sofort die Antwort kennen, den Basisfall , und den zweiten Fall, wo wir die gleiche Funktion mit einem anderen Wert berechnen müssen, den rekursiven Fall .

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.