Lernpfad:Rekursion in Java/Aufrufbaum: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
Arbeitsauftrag
Thi (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „==Der Aufrufbaum== thumb|right|Das pascal'sche Dreieck Durch einen Aufrufbaum wird die schrittweise Lösung eines Problem…“) |
Jneug (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung Markierung: Manuelle Zurücksetzung |
||
| (13 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
==Der Aufrufbaum== | {{Navigation}} | ||
[[Datei:PascalTriangleAnimated2.gif| | == 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. | [[Datei:PascalTriangleAnimated2.gif|frame|right|Visualisierung der Berechnung des Pascalschen Dreiecks.]] 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 | Das [[wikipedia:Pascalsches Dreieck|Pascalsche Dreieck]] kann rekursiv berechnet werden, die jeweils oberhalb liegenden Felder werden addiert und ergeben das darunter liegende Feld (vgl. Animation rechts). | ||
Der untere Aufrufbaum verdeutlicht die Berechnungen, die für die vierte Zeile und die dritte Spalte des | Der untere Aufrufbaum verdeutlicht die Berechnungen, die für die vierte Zeile und die dritte Spalte des Pascalschen Dreiecks benötigt werden: | ||
[[Datei:02_Rekursion_Aufrufbaum_Pascalsche_Dreieck.PNG| | [[Datei:02_Rekursion_Aufrufbaum_Pascalsche_Dreieck.PNG|Aufrufbaum bei der rekursiven Berechnung des Pascalschen Dreiecks.]] | ||
{{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: | |||
* | * <math>f(n) = f(n-2)+f(n-1)</math> für <math>n>1</math> | ||
* | * <math>f(n) = n</math> für <math>n<2</math> | ||
<syntaxhighlight lang="java" line="1" > | <syntaxhighlight lang="java" line="1" > | ||
public int f(n) { | public int f(n) { | ||
if(n > 1) { | |||
return f(n-2) + f(n-1); | |||
} else { | |||
return 1; | |||
} | |||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
Notiere den Aufrufbaum des Methodenaufrufs <math>f(4)</math>. | |||
{{Aufgabe:End}} | |||
{{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}} | ||
Aktuelle Version vom 2. Mai 2025, 08:08 Uhr
Der Aufrufbaum
Visualisierung der Berechnung des Pascalschen Dreiecks.
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 (vgl. Animation rechts).
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]
public int f(n) {
if(n > 1) {
return f(n-2) + f(n-1);
} else {
return 1;
}
}
Notiere den Aufrufbaum des Methodenaufrufs [math]\displaystyle{ f(4) }[/math].
Lösung
