Lernpfad:Rekursion in Java/Aufrufbaum: Unterschied zwischen den Versionen
Jneug (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Jneug (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 10: | Zeile 10: | ||
{{Aufgabe:Start}} | {{Aufgabe:Start}} | ||
Eine Fibonacci-Zahl wird durch die Summe der zwei vorherigen Fibonacci-Zahlen gebildet. | Eine [[wikipedia:Fibonacci-Folge|Fibonacci-Zahl]] wird durch die Summe der zwei vorherigen Fibonacci-Zahlen gebildet. | ||
Mathematisch ausgedrückt: | Mathematisch ausgedrückt: | ||
| Zeile 16: | Zeile 16: | ||
* <math>f(n) = n</math> für <math>n<2</math> | * <math>f(n) = n</math> für <math>n<2</math> | ||
Notieren Sie den Aufrufbaum des Methodenaufrufs f(4). | Notieren Sie den Aufrufbaum des Methodenaufrufs <math>f(4)</math>. | ||
<syntaxhighlight lang="java" line="1" > | <syntaxhighlight lang="java" line="1" > | ||
public int f(n) { | public int f(n) { | ||
| Zeile 29: | Zeile 29: | ||
{{Lösung:Start}} | {{Lösung:Start}} | ||
[[Datei:03_Rekursion_Aufrufbaum_fib_loesung.PNG]] | [[Datei:03_Rekursion_Aufrufbaum_fib_loesung.PNG|Aufrufbaum bei der rekursiven Berechnung von f(4).]] | ||
{{Lösung:End}} | {{Lösung:End}} | ||
Version vom 2. Januar 2019, 14:07 Uhr
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. 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 darunter liegende Feld.
Der untere Aufrufbaum verdeutlicht die Berechnungen, die für die vierte Zeile und die dritte Spalte des Pascalschen Dreiecks benötigt werden:
Eine Fibonacci-Zahl wird durch die Summe der zwei vorherigen Fibonacci-Zahlen gebildet.
Mathematisch ausgedrückt:
- [math]\displaystyle{ f(n) = f(n-2)+f(n-1) }[/math] für [math]\displaystyle{ n\gt 1 }[/math]
- [math]\displaystyle{ f(n) = n }[/math] für [math]\displaystyle{ n\lt 2 }[/math]
Notieren Sie den Aufrufbaum des Methodenaufrufs [math]\displaystyle{ f(4) }[/math].
public int f(n) {
if (n > 1){
return f(n-2) + f(n-1);
}else{
return n;
}
}
