Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


5. Rekursion



Die Rekursion ist ein fundamentales Konzept in der Mathematik und in der Informatik. Die einfache Definition lautet, daß ein rekursives Programm ein Programm ist, das sich selbst aufruft (und daß eine rekursive Funktion eine Funktion ist, die durch sich selbst definiert wird). Ein rekursives Programm kann sich jedoch nicht immer aufrufen, sonst würde es nie abbrechen (und für die Definition einer rekursiven Funktion kann nicht immer sie selbst benutzt werden, sonst hätte die Definition die Gestalt eines geschlossenen Kreises); ein weiteres wesentliches Merkmal ist, daß es eine Abbruchbedingung geben muß, die angibt, wann das Programm aufhören kann, sich selbst aufzurufen (und wann die Funktion nicht durch sich selbst definiert wird). Alle praktischen Berechnungen können rekursiv realisiert werden.

Unser vorrangiges Ziel in diesem Kapitel besteht darin, die Rekursion als ein praktisches Werkzeug zu untersuchen. Zuerst führen wir einige Beispiele an, in denen sie nicht praktikabel ist, wobei wir den Zusammenhang zwischen einfachen mathematischen rekurrenten Beziehungen und einfachen rekursiven Programmen aufzeigen. Danach betrachten wir ein als Prototyp dienendes Beispiel eines auf dem Prinzip »Teile und Herrsche« beruhenden rekursiven Programms des Typs, den wir benutzen, um grundlegende Probleme in verschiedenen späteren Abschnitten dieses Buchs zu lösen. Schließlich erörtern wir, wie die Rekursion aus jedem beliebigen rekursiven Programm entfernt werden kann, und behandeln ein ausführliches Beispiel, in dem aus einem einfachen rekursiven Algorithmus zur Traversierung eines Baumes durch die Beseitigung der Rekursion ein einfacher nichtrekursiver, einen Stapel benutzender Algorithmus wird.

Wie wir sehen werden, lassen sich viele interessante Algorithmen ganz einfach mit rekursiven Programmen ausdrücken, und viele Entwickler von Algorithmen bevorzugen die rekursive Darstellung von Verfahren. Doch es liegt auch sehr oft der Fall vor, daß sich in den Details einer (notwendigerweise) nichtrekursiven Implementation ein ebenso interessanter Algorithmus verbirgt; im vorliegenden Kapitel untersuchen wir Techniken des Auffindens solcher Algorithmen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]