Spiegelbild im Spiegel

Rekursion


Quellen:
D. Skoda, EFS220, Elektronikschule Tettnang
A. Maier, G. Kompa Elektronikschule Tettnang, 2020
E. Fuchs, "Java 9 Grundlagen Programmierung", Herdt Verlag, 2017

Bei der Rekursion oder rekursiven Programmierung ruft sich eine Methode selbst wieder auf.

In diesem Artikel lernst Du den Aufbau von rekursiven Methoden und deren Anwendung kennen.

Die Idee von Rekursion

Orangensaftpresse

Um Rekursion zu verstehen muß der Umgang mit Methoden sitzen. Deshalb zu Beginn nochmal eine kurze Wiederholung. Nehmen wir folgende bekannte Methoden:

public static void main(String[] args) {...}
static int berechneSaftmenge(int orangenzahl){...}

  1. Bestimme mögliche Modifier.
  2. Bestimme Datentypen welche als Rückgabeparameter erlaubt sind.
  3. Nenne die Methodennamen.
  4. Nenne die Parameternamen. Wie viele Parameter sind in einer Parameterliste möglich?

Nun testen wir den Methodenaufruf. Bestimme für jede der gegebenen Methoden einen möglichen Aufruf:

  • public static void presseOrangen(int a){}
  • public static int presseOrangen(int a){}
  • public static void presseOrangen(int a){
      presseOrangen(a-1);
    }

Funktioniert der letzte Methodenaufruf überhaupt?

Rekursion erklärt

Wir betrachten folgendes Beispiel:

private static void pushUp(int amount) {
	if(amount == 0)	return;
	System.out.println("1mal geschafft. Noch "+(amount-1)+"!");
	pushUp(amount-1);
}

Der Methode wird eine bestimmte Anzahl übergeben. Die Methode ruft sich dabei immer wieder selbst auf. Um keine endlose Wiederholung zu erhalten, muss es ein Ende geben. Dies wird durch die zwei folgenden Punkte erreicht

  1. Bei jedem erneuten Aufruf der Methode wird der Wert um eins reduziert.
  2. Falls der Wert Null ist, folgt der return-Befehl.

Mit Hilfe der Rekursion lassen sich wiederholte Abläufe programmieren. Wie ein Spiegelbild im Spiegel ähnelt Rekursion einer Schleife, jedoch können hiermit auch deutlich komplexere Berechnungen, wie wir nachher sehen, gelöst werden. Anderseits ist der Programmablauf bei einer Rekursion oft nicht leicht zu verstehen.

Aufgabe 1 Fakultät

Autoren: D. Skoda, D. Supper

Die Fakultät ist eine mathematische Funktion, welche eine natürlichen Zahl das Produkt aus dieser und aller kleineren natürlichen Zahlen (≥ 1) zuordnet.

  1. Lege eine neues "Java Projekt" mit alt +  Strg  + N namens 07-Rekursion an.
  2. Erstelle die Klasse Fakultaet in welcher der Benutzer die Höhe der Fakultät eingibt.
  3. Schreibe die Methode void notiereFakultaet(int n){ ... }. Die Methode soll bei der Zahl 6 folgende Ausgabe rekursiv erzeugen:
    6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1
  4. Berechne in der Methode int berechneFakultaet(int n){ ... } den Wert der Fakultät. Der Fakultätswert wird rekursiv berechnet und dann zurückgegeben.

    return n * berechneFakultaet(n-1);

Die Ausgabe sollte wie folgt aussehen:

Nenne die Anzahl: 6
6! = 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 720


Aufgabe 2 Ordne zu

Bestimme den Quelltext, damit alle Zahlen von a bis 0 addiert werden. Wähle eine Antwort.
int add(int a){...}

  1. if(a>0) return a-add(a); else return 0;
  2. if(a>0) return a/add(a+1); else return a;
  3. if(a>0) return a+add(a-1); else return 0;
  4. if(a<0) return a+add(a-1); else return 0;

Bestimme den Quelltext, damit alle Zahlen von a bis 1 dividiert werden. Wähle eine Antwort.
static double add(double a){...}

  1. if(a>1) return a/add(a-1); else return 0;
  2. if(a>1) return a/add(a-1); else return 1;
  3. if(a>1) return a/add(a+1); else return 1;
  4. if(a<1) return a-add(a-1); else return 2;

Aufgabe 3 Die Ackermannfunktion

Quellen:
Dean Skoda, EFS220, Elektronikschule Tettnang, 2022
Hans U. Simon, Ruhr-Universität Bochum, Germany, 2004
https://de.wikipedia.org/wiki/Ackermannfunktion

Im Jahre 1928 präsentierte Wilhelm Ackermann eine Funktion, die sogenannte Ackermannfunktion:
$a(0, y) = y + 1$ für alle $y\ge0$
$a(x, 0) = a(x − 1, 1)$ für alle $x ≥ 1$
$a(x, y) = a(x − 1, a(x, y − 1))$ für alle $x, y ≥ 1$

  1. Berechne den Wert für $a(0,1)$, $a(0,2)$, $a(0,3)$ ...
  2. Berechne den Wert für $a(1,0)$, $a(2,0)$.
  3. Zeige das der Wert für $a(3,0)=5$ ist.
  4. Berechne $a(2,2)$.
  5. Erstelle die Klasse Ackermann und definiere die Methode private static int ack(int x, int y). Programmiere mit Hilfe des Pseudocodes und überprüfe Deine Ergebnisse.
  1. $a(0,1)=2$
    $a(0,2)=3$
    $a(0,3)=4$
  2. $a(1,0)=2$
    $a(2,0)=3$

Entspann dich erstmal ...



Der Mathematikerspruch

Um Rekursion zu verstehen, muß man zunächst Rekursion verstehen.

Wortliste und Satzbausteine



die Methode, -n Eine Methode ist ein ausgelagerter Programmteil.
die Rekursion, -en innerhalb einer Methode wird die identische Methode nochmals aufgerufen.