Lernpfad:Rekursion in Java/Aufrufbaum

Der Aufrufbaum

Das pascal'sche Dreieck

Durch einen Aufrufbaum wird die schrittweise Lösung eines Problems dargestellt. Im Aufrufbaum werden die Parameter und die Rückgaben der Methode visualisiert. Gerade bei Methoden mit mehreren rekursiven Aufrufen verdeutlicht der Aufrufbaum die Ausführung.

Das pascalsche Dreieck kann rekursiv berechnet werden, die jeweils oberhalb liegenden Felder werden addiert und ergeben das untere Feld.

Der untere Aufrufbaum verdeutlicht die Berechnungen, die für die vierte Zeile und die dritte Spalte des pascal'schen Dreiecks benötigt werden:

Arbeitsauftrag

Eine Fibonacci-Zahl wird durch die Summe der zwei vorherigen Fibonacci-Zahlen gebildet.

• Mathematisch ausgedrückt:
  • f(n) = f(n-2)+f(n-1) für n>1,
  • f(n) = n für n<2

Notieren Sie den Aufrufbaum des Methodenaufrufs f(4).

public int f(n) {
  if (n > 1){
    return f(n-2) + f(n-1);
  }else{
    return n;
  }
}

Lösung