If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Kurs: Informatik > Lerneinheit 1

Lektion 6: Rekursive Algorithmen
Informatik
Informatik
Algorithmen
Rekursive Algorithmen
© 2024 Khan AcademyNutzungsbedingungenDatenschutzerklärungCookie-Meldung

Rekursive Fakultät

Google Classroom
Für positive Werte von n, bedeutet n!, wie bereits gesehen, ein Produkt von Zahlen von n bis 1: Also n! = n⋅(n−1)⋯2⋅1. . Dabei ist (n−1)⋯2⋅1 eine andere Schreibweise für (n−1)!, Und so können wir sehen, dass n!=n⋅(n−1)! ist. Hast du gemerkt, was wir gerade gemacht haben? Wir haben n geschrieben als ein Produkt, in dem einer der Faktoren (n−1)! ist. _Du kannst n! berechnen indem du (n−1)! berechnest und dann das Ergebnis von (n−1)! mit n multiplizierst.Du kannst die Fakultät von n berechnen, indem du zuerst die Fakultät von n−1 berechnest. Wir sagen, dass die Berechnung von (n−1)! ein Subproblem ist, das wir lösen müssen, um n zu berechnen!
Als Beispiel berechnen wir 5!.
  • Du kann 5! durch 5⋅4! berechnen.
  • Jetzt müssen wir das Unterproblem der Berechnung von 4! lösen, indem wir 4⋅3! berechnen.
  • Dafür müssen wir das Unterproblem von 3 ! lösen, was 3⋅2! ist.
  • Jetzt ist 2! dran, das ist 2⋅1!.
  • Jetzt müssen wir 1! berechnen. Man kann sagen, dass 1! gleich 1 ist, weil es das Produkt aller ganzen Zahlen von 1 bis 1 ist. Oder du kannst die Formel anwenden, nach der 1!=1⋅0! ist. Lass es uns tun, indem wir die Formel anwenden.
  • Wir definieren 0!=1.
  • Jetzt können wir 1!=1⋅0!=1 berechnen .
  • Nachdem wir 1!=1 berechnet habe, kannst du 2!=2⋅1!=2. bestimmen
  • Nach 2!=2, kommt 3!=3⋅2!=6.
  • Nach 3!=6, bestimmen wir 4!=4⋅3!=24.
  • Schlussendlich, nach 4!=24, können wir 5!=5⋅4!=120 berechnen.
So jetzt haben wir einen anderen Weg gefunden, den Wert von n!, für alle natürlichen Zahlen n zu bestimmen:
  • Wenn n=0 ist, dann deklarieren wir, dass n!=1 ist.
  • Andernfalls muss n positiv sein. Löse das Unterproblem der Berechnung von (n−1)! und multipliziere dieses Ergebnis mit n und deklariere n! gleich dem Ergebnis dieses Produktes.
Wenn wir 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.

Willst du an der Diskussion teilnehmen?

Anmelden
Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.