Arbeitsblätter für JavaKara

Einführung in Java: Ergänzungen zur Rekursion

Autor: Horst Gierhardt

Die Rekursion haben wir uns so vorgestellt, dass beim rekursiven Aufruf einer Methode sich der Computer merkt, wo er eine Methode verlässt, um danach an der gleichen Stelle weiter machen zu können. Anschaulich könnte man das mit einem Stapel (engl.: stack) darstellen. Beim ersten Aufruf wird die Rückkehradresse auf ein Blatt Papier geschrieben, beim zweiten Aufruf wird wieder die Rückkehradresse auf ein neues Blatt geschrieben und dieses Blatt auf das erste gelegt (engl.: to push) und so weiter. Am Ende wird das oberste Blatt zuerst vom Stapel genommen (engl.: to pop) und sich bis zum untersten Blatt zurück gearbeitet.

Beispiele für rekursive Strukturen im weitesten Sinne:

Geschichten innerhalb von Geschichten; Filme innerhalb von Filmen: in Filmen treten oft Rückblendungen innerhalb von Rückblendungen auf, wobei man am Ende wieder bei der Haupthandlung landet. Beliebt sind Filme über Filmteams, die einen Film drehen. Besonders krasses Beispiel: Hellzapoppin, deutsche Fassung: In der Hölle ist der Teufel los!
Bach setzt häufig musikalische Stapel ein: Von der Grundtonart wird in die zweite Tonart gewechselt (to push), daraus nochmals in eine dritte Tonart gepusht und dann wieder zurück in die zweite gepoppt mit anschließendem Pop in die Grundtonart, was vom Zuhörer als Erleichterung empfunden wird.
Stapel in der Sprache:
1. ,,Die notorische Eigenheit der deutschen Sprache, das Verbum ans Ende des Satzes zu stellen, über welche lustige Geschichten von geistesabwesenden Professoren, die einen Satz beginnen, die ganze Vorlesung, die langweilig empfunden wird, weiterreden und damit aufhören, dass sie eine Kette von Verben herunterleiern, wobei die Zuhörer, für die der Stapel schon längst jeglichen Zusammenhang verloren hat, völlig verwirrt werden, erzählt werden, ist ein gutes Beispiel für linguistisches Pushen und Poppen.''
2. ,,Die Kinder, die sich, da sie, weil sie schwimmen waren, sich ämüsierten, gut verstanden, hatten sich erkältet.''
```
            Die Kinder,
                  die sich,
                      da sie,
                           weil sie schwimmen waren,
                      sich amüsierten,
                 gut verstanden,
            hatten sich erkältet.
            
```
3. Ein besonders krasses Beispiel findet man von Christian Morgenstern in der Vorrede zu den Galgenliedern. Einer seiner Sätze endet mit "...kaum mehr zu unterschlagen versucht werden zu wollen vermag - gegenübergestanden und beigewohnt werden zu dürfen gelten lassen zu müssen sein möchte."
4. Merkwürdige Sätze:
  1. Dieser Satz enthält fünf Wörter.
  2. Der Satz ,,Der Satz enthält fünf Wörter.'' enthält fünf Wörter.
  3. Der Satz ,,Der Satz Der Satz enthält fünf Wörter enthält fünf Wörter.'' enthält fünf Wörter.
  4. Der Satz ,,Der Satz ist unendlich lang.'' ist unendlich lang.
  5. Der Satz ,,Der Satz ,,Der Satz ,,Der Satz ... ist unendlich lang.'' ist unendlich lang.'' ist unendlich lang.'' ist unendlich lang.
  6. Dieser Satz ist falsch.
  7. Der Satz ,,Dieser Satz ist falsch.'' ist falsch.
  8. Der folgende Satz ist falsch. Der vorhergehende Satz ist richtig.
Rekursion in der Mathematik:
1. Definition der natürlichen Zahlen:
  0 ist eine natürliche Zahl.
  Der Nachfolger einer natürlichen Zahl ist wieder eine natürliche Zahl.
2. Die Multiplikation mit einer natürlichen Zahl wird auf die Addition zurückgeführt:
  Das n-fache einer Zahl ist das (n-1)-fache der Zahl plus der Zahl.
  Ende der Rekursion: Das 1-fache einer Zahl ist die Zahl selbst.
3. Die Potenzierung mit einem natürlichen Exponenten wird auf die Multiplikation zurückgeführt:
  Das n-te Potenz einer Zahl ist die (n-1)-te Potenz der Zahl multipliziert mit der Zahl.
  Ende der Rekursion: Die 1-te Potenz einer Zahl ist die Zahl selbst.
4. Die Fakultät einer Zahl natürlichen Zahl ist rekursiv definiert:
  n! = (n-1)! ·n
  0! = 1
5. Die in der Mathematik wohl berühmteste Zahlenfolge besteht aus den Fibonacci-Zahlen. Beginnt man mit der Nummerierung bei 1, dann ist die n-te Fibonacci-Zahl fibo(n) rekursiv definiert durch:
  fibo(1) = 1
  fibo(2) = 1
  fibo(n) = fibo(n-2) + fibo(n-1) für n größer als 2.
  Fibonacci-Zahlen treten in den verschiedensten Situationen auf, z.B. beim Pflanzenwachstum oder bei der Untersuchung von Aktiencharts.