Show description

Es gibt sogar Programmiersprachen2, die keine Schleifen kennen, sondern Wiederholung durch Rekursion ausgedrückt werden muss. Auch Rekursionen kann man meistens mit Hilfe von Iteration simulieren3. Oft sind die rekursiven Lösungen einfacher zu verstehen, verbrauchen aber für die Abarbeitung der Rekursion mehr Speicherplatz. 1 Fakultät Als erstes Beispiel für rekursive Algorithmen betrachten wir die Funktion Fakultät. Die mathematische Bezeichnung der Fakultät ist n!. Sie wird als das Produkt der ersten n natürlichen Zahlen durch die Formel n!

Aelteste); // rekursvier Knotenvergleich } private boolean istGleichRek(final Knoten dieser, final Knoten jener) { if (dieser == null || jener == null) // eine der Listen zu Ende return dieser == null && jener == null; // ob auch die andere? verbindung)); // den Wert in den neuen Knoten kopieren, den Rest rekursiv kopieren } 1 static-Methoden können den Typparameter der generischen Klasse nicht benutzen; sie müssen selber als generische Methoden vereinbart werden. 3. (auf Seite 21) gesehen haben, bieten Reihungen zu verketteten Listen eine Alternative.

1 ˜ 2 ˜ 3 ˜ … ˜ (n-1) ˜ n = (n-1)! ˜ n möglich: fakultaetRekursiv(n) == n * fakultaetRekursiv(n-1) static int fakultaetRekursiv(int n) { // requires n > 0 if (n <= 1) return 1; else return n * fakultaetRekursiv(n-1); // return n <= 1 ? 1 : n * fakultaetRekursiv(n-1); // } für n t 2: 1 Der Nachteil der rekursiven Lösung gegenüber dem iterativen Programm ist der zusätzliche Verbrauch von Speicher: Die rekursiven Aufrufe werden auf dem Stapel (stack) abgelegt2. Die Größe des nötigen Speichers ist also proportional zum Parameter.