Rekursion - Programmieren Spielend Gelernt mit dem Java-Hamster-Modell - page 318

Kapitel 17
Rekursion
17 .
In diesem Kapitel werden wir kein neues Sprachkonstrukt kennenlernen. Vielmehr wird mit dem
Prinzip der Rekursion eine Alternative zu den Wiederholungsanweisungen aus Kapitel 10 einge-
führt, mit dem sich bestimmte Probleme wesentlich einfacher, verständlicher, intuitiver und kom-
pakter lösen lassen. Programme bzw. Funktionen, die Wiederholungsanweisungen einsetzen, wer-
den auch iterative Programme bzw. iterative Funktionen genannt. Programme bzw. Funktionen, die
vom Rekursionsprinzip Gebrauch machen, werden dementsprechend als rekursive Programme bzw.
rekursive Funktionen bezeichnet. Sie kommen im Allgemeinen ohne Wiederholungsanweisungen
und mit weniger Variablen aus als äquivalente iterative Programme.
Prinzipiell ist das Prinzip der Rekursion entbehrlich. Man kann nämlich beweisen, dass zu jedem
rekursiven Programm ein äquivalentes iteratives Programm existiert. Nichtsdestotrotz werden Ihnen
einige Beispiele in diesem Kapitel die Vorteile rekursiver Programme illustrieren.
Allerdings sei an dieser Stelle auch angemerkt, dass gerade Programmieranfänger häufig Probleme
haben, das Rekursionsprinzip zu verstehen und gezielt einzusetzen. Schauen Sie sich deshalb ganz
genau die Beispiele in diesem Kapitel an und versuchen Sie, alle Übungsaufgaben zu bearbeiten. Das
Hamster-Modell wird Sie insbesondere durch sein visuelles Feedback beim Ausführen von Hamster-
Programmen beim Erlernen der Rekursion unterstützen.
Dieses Kapitel ist so aufgebaut, dass nach einer einleitenden Motivation des Rekursionsprinzips in
Abschnitt 1 in Abschnitt 2 zunächst ein paar Begriffe definiert werden. In Abschnitt 3 wird das Re-
kursionsprinzip danach anhand einiger Beispiele und Anmerkungen veranschaulicht. In Abschnitt
4 werden rekursive Funktionen eingeführt, nachdem in den Abschnitten 1 bis 3 lediglich rekur-
sive Prozeduren behandelt worden sind. Die Abschnitte 5 und 6 erläutern die Auswirkungen der
Definition von lokalen Variablen bzw. Parametern in rekursiven Funktionen. Abschnitt 7 stellt das
Backtracking-Verfahren vor, ein Lösungsverfahren für eine bestimmte Klasse von Problemen, das
auf dem Rekursionsprinzip aufbaut. Anhand einiger Beispielprogramme wird in Abschnitt 8 das
Rekursionsprinzip demonstriert. Abschnitt 9 enthält ein paar Übungsaufgaben, an denen Sie die
Entwicklung rekursiver Programme selbstständig einüben können.
17.1 Motivation
Schauen Sie sich folgende Hamster-Aufgabe an: Der Hamster soll bis zur nächsten Wand laufen,
kehrt machen und zum Ausgangspunkt zurücklaufen. Wir haben diese Aufgabe bereits in Kapitel
14.10.1 durch den Einsatz einer Variablen und einer Wiederholungsanweisung gelöst:
void hinUndZurueck() {
int schritte = 0;
// laufe zur Wand