Lernpfad:Rekursion in Java

Dieser Lernpfad ist derzeit noch im Aufbau.

Definition

Inhalt Lernpfad Rekursion in Java
Rekursion in Java Definition Aufrufstapel Aufrufbaum Rekursion bei Schachproblemen Selbst eine rekursive Methode schreiben
Inhalt bearbeiten

Einführung Rekursion

In diesem Lernpfad lernst du die Grundlagen der rekursiven Programmierung kennen. Dieses Prinzip wird in vielen Anwendungen verwendet.

Definition: Eine rekursive Methode besteht aus

1. einer Abbruchbedingung
2. einer Reduktion des Problems
3. mindestens einem Aufruf der rekursiven Methode

Erstes Beispiel Rekursion: Fakultät

Mit der folgenden Methode wird die Fakultät berechnet.
Die Fakultät ist ein mathematischer Operator und wird durch ein Ausrufezeichen dargestellt
4! = 4*3*2*1; (Das Ausrufezeichen steht dabei hinter der Zahl).
In Java wird dieser Operator bzw. diese Funktion nicht zur Verfügung gestellt, deshalb muss sie programmiert werden. Der Quelltext für die Methode sieht wie folgt aus:

public int fakultät (int n){
  if (n < 2){
    return 1;
  }else{
    return n*fakultät (n-1);
  }
}

Arbeitsauftrag

Aufgabe 1.1: Ordnen Sie den Quelltext-Teilen die einzelnen Bestandteile einer rekursiven Methode zu.
public int fakultät (int n){

if (n < 2){	Abbruchbedingung
return 1;	Abbruch der Rekursion
return n*fakultät (n-1);	rekursiver Aufruf	Reduktion des Problems

Der Aufrufstapel

Aufrufstapel der Methode Fakultät

Intern werden die Methodenaufrufe einer rekursiven Methode auf einem Stapel gespeichert. Die Methoden, die ganz oben auf dem Stapel liegen, werden zuerst abgearbeitet. Danach wird das Resultat der Methode verwendet, um die darunterliegenden Methoden zu berechnen.

Arbeitsauftrag

Die Methode z	Ergänzen Sie den Aufrufstapel zu dem Methodenaufruf z(5) .
public int z(x) { if (x > 1){ return a + z(x - 2); }else{ return 1; } }	z(1) 1 z(3) z(5) z(5) z(5) z(5) 5+4=9

Der Aufrufbaum

Durch einen Aufrufbaum wird die schrittweise Lösung eines Problems dargestellt. Im Aufrufbaum werden die Parameter und die Rückgaben der Methode visualisiert. Der rechte Aufrufbaum verdeutlicht die Berechnungen, die für die Fakultät gemacht werden müssen:

Arbeitsauftrag

Ergänzen Sie den Aufrufbaum zu dem Methodenaufruf z(5) .

public int z(x) {
  if (x > 1){
    return a + z(x - 2);
  }else{
    return 1;
  }
}