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

Eigenschaften von rekursiven Algorithmen

Hier ist die Grundidee hinter rekursiven Algorithmen:
Um ein Problem zu lösen, lösen wir ein Unterproblem, das eine kleinere Instanz des gleichen Problems ist, und verwenden dann die Lösung für diese kleinere Instanz, um das ursprüngliche Problem zu lösen.
Bei der Berechnung von n! haben wir das Problem der Berechnung von n! (Das ursprüngliche Problem) durch die Lösung des Unterproblems der Berechnung der Fakultät einer kleineren Zahl gelöst, das heißt, die Berechnung von (n1)! (Das ist die kleinere Instanz des gleichen Problems) und dann haben wir die Lösung des Subproblems verwendet, um den Wert von n! zu berechnen.
Damit ein rekursiver Algorithmus funktioniert, müssen die Unterprobleme schließlich zum Basisfall gelangen. Bei der Berechnung von n! werden die Unterprobleme kleiner und kleiner, bis wir 0! berechnen. Du musst dafür sorgen, dass du irgendwann den Basisfall triffst.
Ein Beispiel: Was passiert, wenn wir mit unserer rekursiven Methode versuchten, die Fakultät einer negativen Zahl zu berechnen? Um (1)! zu berechnen würden wir zuerst versuchen, (2)! zu berechnen, so dass man das Ergebnis mit 1 multiplizieren könnte. Aber um (2)! zu berechnen, würden wir (3)! berechnen, so dass man das Ergebnis mit 2 multiplizieren könnte. Und dann würden wir versuchen, (3)! zu berechnen, und so weiter. Sicher, die Zahlen werden immer kleiner, aber sie entfernen sich auch immer weiter vom Basisfall 0!. Wir würden niemals zu einem Ergebnis gelangen..
Selbst wenn du garantieren kannst, dass der Wert von n nicht negativ ist, kannst du immer noch in Schwierigkeiten geraten, wenn du die Subprobleme nicht allmählich kleiner machst. Hier ist ein Beispiel: Nehmen wir die Formel n!=n(n1)! Und dividieren beide Seiten durch n. Wir erhalten n!/n=(n1)!. Wir definieren eine neue Variable, m, und setzen sie gleich n+1. Da unsere Formel für jede positive Zahl gilt, ersetzen wir n durch m und erhalten m!/m=(m1)!. Da m=n+1 haben wir jetzt (n+1)!/(n+1)=(n+11)!. Wir tauschen die Seiten und vereinfachen n+11=n. Damit erhalten wir n!=(n+1)!/(n+1). Diese Formel verführt uns dazu zu glauben, dass wir n! berechnen können indem wir zuerst (n+1)! berechnen und dann das Ergebnis durch n+1 dividieren. Aber um (n+1)! zu berechnen musst du (n+2)! berechnen, dann (n+3)! und so weiter. Wir würden nie den Basisfall von 0\ erreichen. Warum nicht? In jeder Rekursion musst Du den Wert einer größeren Zahl berechnen, nicht eine kleineren Zahl. Wenn n positiv ist, würden wir niemals den Basisfall von 0 treffen.
Wir können für die Rekursion zwei einfache Regeln formulieren:
  1. Jeder rekursive Anruf sollte auf einer kleineren Instanz des gleichen Problems arbeiten, das heißt, ein kleineres Teilproblem.
  2. Die rekursiven Anrufe müssen schließlich einen Basisfall erreichen, der ohne weitere Rekursion gelöst wird.
Wenden wir uns wieder den russischen Puppen zu. Wir können sehen, dass jede Puppe alle kleineren Puppen (analog zum rekursiven Fall) umschließt, bis hin zur kleinsten Puppe, die keine anderen Puppen umschließt (Basisfall).

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?

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