|
|
| Zeile 4: |
Zeile 4: |
|
| |
|
| =Einführung Rekursion= | | =Einführung Rekursion= |
| In diesem Lernpfad lernst du die Grundlagen der ''rekursiven Programmierung'' kennen. Dieses Prinzip wird in vielen Anwendungen verwendet. | | In diesem Lernpfad lernst du die Grundlagen der ''rekursiven Programmierung'' kennen. Dieses Prinzip wird in vielen Anwendungen verwendet. |
| | |
| {{Schublade |
| |
| Definition: Eine rekursive Methode besteht aus
| |
| #einer Abbruchbedingung
| |
| #einer Reduktion des Problems
| |
| #mindestens einem Aufruf der rekursiven Methode
| |
| | Farbe=#c7d210}}
| |
| ==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:
| |
| <syntaxhighlight lang="java" line="1" >
| |
| public int fakultät (int n){
| |
| if (n < 2){
| |
| return 1;
| |
| }else{
| |
| return n*fakultät (n-1);
| |
| }
| |
| }
| |
| </syntaxhighlight>
| |
| {{Aufgabe:Start}}
| |
| Aufgabe 1.1: Ordnen Sie den Quelltext-Teilen die einzelnen Bestandteile einer rekursiven Methode zu.<br />
| |
| public int fakultät (int n){
| |
| <zuordnung>
| |
| :: if (n < 2){::Abbruchbedingung
| |
| :: return 1;::Abbruch der Rekursion
| |
| :: return n*fakultät (n-1);::rekursiver Aufruf::Reduktion des Problems
| |
| </zuordnung>
| |
| {{Aufgabe:End}}
| |
| | |
| ==Der Aufrufstapel==
| |
| [[Datei:01_Rekursion_Aufrufstack_Fakultaet.png |right|800px| thumb| 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.
| |
| | |
| {{Aufgabe:Start}}
| |
| {| class="wikitable"
| |
| ! Die Methode z
| |
| ! Ergänzen Sie den Aufrufstapel zu dem Methodenaufruf z(5) .
| |
| |-
| |
| | <syntaxhighlight lang="java" line="1" >
| |
| public int z(x) {
| |
| if (x > 1){
| |
| return a + z(x - 2);
| |
| }else{
| |
| return 1;
| |
| }
| |
| }
| |
| </syntaxhighlight>
| |
| |
| |
| {|class="wikitable"
| |
| |
| |
| |
| |
| |z(1)
| |
| |1
| |
| |
| |
| |-
| |
| |
| |
| | z(3)
| |
| |
| |
| |
| |
| |
| |
| |-
| |
| | z(5)
| |
| | z(5)
| |
| | z(5)
| |
| | z(5)
| |
| | 5+4=9
| |
| |-
| |
| |}
| |
| |}
| |
| {{Lösung:Start}}
| |
| | |
| {|class="wikitable"
| |
| |
| |
| |
| |
| |z(1)
| |
| |1
| |
| |
| |
| |-
| |
| |
| |
| | z(3)
| |
| | z(3)
| |
| | 3+1=4
| |
| |
| |
| |-
| |
| | z(5)
| |
| | z(5)
| |
| | z(5)
| |
| | z(5)
| |
| | 5+4=9
| |
| |-
| |
| |}
| |
| {{Lösung:End}}
| |
| {{Aufgabe:End}}
| |
| | |
| ==Der Aufrufbaum==
| |
| [[Datei:PascalTriangleAnimated2.gif|thumb|right|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:
| |
| [[Datei:02_Rekursion_Aufrufbaum_Pascalsche_Dreieck.PNG|02_Rekursion_Aufrufbaum_Pascalsche_Dreieck.PNG]]
| |
| | |
| {{Aufgabe:Start}}
| |
| 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).
| |
| <syntaxhighlight lang="java" line="1" >
| |
| public int f(n) {
| |
| if (n > 1){
| |
| return f(n-2) + f(n-1);
| |
| }else{
| |
| return n;
| |
| }
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| {{Lösung:Start}}
| |
| [[Datei:03_Rekursion_Aufrufbaum_fib_loesung.PNG]]
| |
| {{Lösung:End}}
| |
| {{Aufgabe:End}}
| |
Dieser Lernpfad ist derzeit noch im Aufbau.
