Eigenschaften von rekursiven Algorithmen

Hier ist die Grundidee hinter rekursiven Algorithmen:

Bei der Berechnung von $n!$n, ! haben wir das Problem der Berechnung von $n!$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 $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, ! (Das ist die kleinere Instanz des gleichen Problems) und dann haben wir die Lösung des Subproblems verwendet, um den Wert von $n!$n, ! zu berechnen.

Damit ein rekursiver Algorithmus funktioniert, müssen die Unterprobleme schließlich zum Basisfall gelangen. Bei der Berechnung von $n!$n, ! werden die Unterprobleme kleiner und kleiner, bis wir $0!$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)!$left parenthesis, minus, 1, right parenthesis, ! zu berechnen würden wir zuerst versuchen, $(-2)!$left parenthesis, minus, 2, right parenthesis, ! zu berechnen, so dass man das Ergebnis mit $-1$minus, 1 multiplizieren könnte. Aber um $(-2)!$left parenthesis, minus, 2, right parenthesis, ! zu berechnen, würden wir $(-3) !$left parenthesis, minus, 3, right parenthesis, ! berechnen, so dass man das Ergebnis mit $-2$minus, 2 multiplizieren könnte. Und dann würden wir versuchen, $(-3)!$left parenthesis, minus, 3, right parenthesis, ! zu berechnen, und so weiter. Sicher, die Zahlen werden immer kleiner, aber sie entfernen sich auch immer weiter vom Basisfall $0!$0, !. Wir würden niemals zu einem Ergebnis gelangen..

Selbst wenn du garantieren kannst, dass der Wert von $n$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 \cdot (n-1)!$n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! Und dividieren beide Seiten durch $n$n. Wir erhalten $n! / n = (n-1)!$n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !. Wir definieren eine neue Variable, $m$m, und setzen sie gleich $n + 1$n, plus, 1. Da unsere Formel für jede positive Zahl gilt, ersetzen wir $n$n durch $m$m und erhalten $m! / m = (m-1)!$m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !. Da $m = n + 1$m, equals, n, plus, 1 haben wir jetzt $(n + 1)! / (n + 1) = (n+1-1)!$left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis, equals, left parenthesis, n, plus, 1, minus, 1, right parenthesis, !. Wir tauschen die Seiten und vereinfachen $n + 1-1 = n$n, plus, 1, minus, 1, equals, n. Damit erhalten wir $n! = (n+1)! / (n + 1)$n, !, equals, left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis. Diese Formel verführt uns dazu zu glauben, dass wir $n!$n, ! berechnen können indem wir zuerst $(n + 1)!$left parenthesis, n, plus, 1, right parenthesis, ! berechnen und dann das Ergebnis durch $n+1$n, plus, 1 dividieren. Aber um $(n+1)!$left parenthesis, n, plus, 1, right parenthesis, ! zu berechnen musst du $(n+2)!$left parenthesis, n, plus, 2, right parenthesis, ! berechnen, dann $(n + 3)!$left parenthesis, n, plus, 3, right parenthesis, ! 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$n positiv ist, würden wir niemals den Basisfall von 0 treffen.

Wir können für die Rekursion zwei einfache Regeln formulieren:

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.