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! 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 (n1)! (n-1)! (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)! (-1)! zu berechnen würden wir zuerst versuchen, (2)! (-2)! zu berechnen, so dass man das Ergebnis mit minus, 1 multiplizieren könnte. Aber um (2)! (-2)! zu berechnen, würden wir (3)! (-3) ! berechnen, so dass man das Ergebnis mit minus, 2 multiplizieren könnte. Und dann würden wir versuchen, (3)! (-3)! 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..
Even if you can guarantee that the value of n is not negative, you can still get into trouble if you don't make the subproblems progressively smaller. Here's an example. Let's take the formula n!=n(n1)! n! = n \cdot (n-1)! and divide both sides by n, giving n!/n=(n1)! n! / n = (n-1)! . Let's make a new variable, m, and set it equal to n, plus, 1. Since our formula applies to any positive number, let's substitute m for n, giving m!/m=(m1)! m! / m = (m-1)! . Since m, equals, n, plus, 1, we now have (n+1)!/(n+1)=(n+11)! (n+1)! / (n+1) = (n+1-1)! . Switching sides and noting that n, plus, 1, minus, 1, equals, n gives us n!=(n+1)!/(n+1) n! = (n+1)! / (n+1) . This formula leads us to believe that you can compute n! n! by first computing (n+1)! (n+1)! and then dividing the result by n, plus, 1. But to compute (n+1)! (n+1)! , you would have to compute (n+2)! (n+2)! , then (n+3)! (n+3)! , and so on. You would never get to the base case of 0. Warum nicht? Because each recursive subproblem asks you to compute the value of a larger number, not a smaller number. If n is positive, you would never hit the base case of 0.
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.