Rekursiver Algorithmus

T

ToBe4minimal

Mitglied
Hallo,

ich schreibe morgen Algodat und lerne gerade das letzte Thema, die Rekursion, die ich überhaupt net in meinen Schädel bekomme.

Als Übungsaufgabe hatten wir folgende Aufgabe:

1 Algorithmus f(x, y)
2 Input: Zwei natürliche Zahlen x und y
3 Output: ?
4
5 if (x ≤ 0) then
6 return x + y
7 else
8 if (y ≤ 0) then
9 return x * y
10 else
11 return f(x/2, 2) + f(1, y-1)

Welchen Wert liefert ein Aufruf von f(4, 3)? In welcher Reihenfolge und mit welchen
Parametern wird f() dabei rekursiv aufgerufen? Geben Sie die Reihenfolge der Aufrufe
explizit an.


So, ich hab das Ding jetzt mal in Eclipse programmiert. Eclipse berechnet mir bei dieser Aufgabe für f(4,3) jetzt 10. Ich versteh aber nicht, wie das Programm auf dieser Ergebnis kommt.

Vor allem verstehe ich nicht, was hier return f(x/2, 2) + f(1, y-1) berechnet wird.

f(x/2, 2) + f(1, y-1)
f(4/2, 2) + f(1, 3-1) ergibt
f(2, 2) + f(1, 2)


OK, und weiter???


Wäre echt toll wenn mir jemand helfen könnte.
Ich verstehe vor allem nicht, was das mit dieser Rekursion auf sich hat.
Ist bei uns im Skript total doof erklärt...

:rtfm:


LG
Tobi
 
M

Marco13

Top Contributor
Rekursion? Dazu gabs kürzlich einen Blog-Eintrag: http://www.java-forum.org/blogs/landei/124-rekursion-verstehen.html

In diesem Fall kann man sich die Aufrufe als einen Baum vorstellen (und auch so aufmalen, das geht... mit Bleistift und Papier besser als so... :D )
Code: 
            f(4,3)
            3.Fall
              /\
             /  \
            /    \
           /      \
        f(2, 2)  +  f(1, 2)
        3.Fall           ....
          /\
         /  \
        /    \
       /      \
    f(1,2)   +   ...  
    3.Fall
      /\
     /  \
    /    \
   /      \
f(0,2)   +  ....
1.Fall:2

Unten links würde jetzt "2" zurückgegeben, rechts davon vielleicht 3 oder so, dann wüßte man, dass das "f(1,2)" aus der vorletzten Zeile den Wert 2+3 nach oben zurückgibt....
 
Appleleptiker

Appleleptiker

Mitglied
Die Rekursion kann man super anhand der Lösung eines rekursiven Algorithmus für die Berechnung einer Fakultät beschreiben.

Java: 
fakultät_rekursiv(n)
{
if n <= 1
 return 1;
else return ( n * fakultät_rekursiv(n-1) )
}

Die Funktion ruft sich in diesem Moment also selbst auf. Nehmen wir mal an, ich übergebe die Zahl 4 an die rekursive Methode:

Code: 
fakultät_rekursiv(4) = 4 * 3 * 2 * 1

Die 4 kann man ja noch verstehen. Versuche doch mal, nachzuvollziehen, welches Ergebnis fakultät(3) zurückgeben würde? Prinzipiell erstmal nur die 3, multipliziert mit dem Ergebnis von fakultät_rekursiv(2), welches eigentlich auch erstmal nur die 2 zurückliefert - multipliziert mit dem Ergebnis von fakultät_rekursiv(1).

Es wir also im Prinzip nur verkettet, immer und immer wieder, bis die Funktion etwas anderes als Return-Ergebnis ausgibt.
 
M

Marco13

Top Contributor
Hast du dir den Baum mal aufgemalt? An den Blättern sollten dann Zahlen stehen (die Blätter sind die Basisfälle, bei denen keine weiteren Rekursiven Aufrufe mehr gemacht werden). Und dor WO rekursive Aufrufe gemacht wurden, werden die Ergebnisse der beiden Aufrufe addiert (wegen "f(..)+f(...)")
 
T

ToBe4minimal

Mitglied
Marco13 hat gesagt.:
Hast du dir den Baum mal aufgemalt? An den Blättern sollten dann Zahlen stehen (die Blätter sind die Basisfälle, bei denen keine weiteren Rekursiven Aufrufe mehr gemacht werden). Und dor WO rekursive Aufrufe gemacht wurden, werden die Ergebnisse der beiden Aufrufe addiert (wegen "f(..)+f(...)")
Zum Vergrößern anklicken....


Hab ich und ich kann deinen Anfang auch nachvollziehen, weiß aber nicht was ich hinschreiben soll wo Du die ... hingemacht hast...
 
T

ToBe4minimal

Mitglied
Code: 
    f(4,3)
            3.Fall
              /\
             /  \
            /    \
           /      \
        f(2, 2)  +  f(1, 2)
        3.Fall          
          /\
         /  \
        /    \
       /      \
    f(1,2) + f(1, 1) 
    3.Fall
      /\
     /  \
    /    \
   /      \
f(0,2)   +  f(1, 0)
1.Fall:2


So oder was??

Und wie wird das dann zusammen gerechnet??
Und was ist das Ergebnis??
Stimmt denn jetzt die 10, was Eclipse berechnet hat??
 
faetzminator

faetzminator

Gesperrter Benutzer
Wieso sollte es nicht stimmen, wenn "Eclipse" das ausgibt ???:L ? Da könnte höchstens ein Programmierfehler schuld sein. Um die Rekursion zu verstehen, könntest du einen Parameter für die Rekursionstiefe hinzufügen. Bei jedem Aufruf von f() erhöhst du diesen einfach um 1. Beim Betreten der Methode kannst du Anzahl Leerzeichen = Tiefe * 2 und danach die beiden Parameter übergeben. Beispiel, wir haben folgendes (Methode gibt y=x^n zurück, wobei y>=2000):
Java: 
public static int f(int x) {
    if (x < 2000) {
        return f(x * x);
    }
    return x;
}
Java: 
public static int f(int x, int level) {
    for (int i = 0; i < level; i++) {
        System.out.print("  ");
    }
    System.out.println("f(" + x + ")");
    if (x < 2000) {
        return f(x * x, level + 1);
    }
    return x;
}
Wenn wir nun [c]f(7, 0)[/c] aufrufen, kriegen wir folgende Ausgabe:
Code: 
f(7)
  f(49)
    f(2401)
 
T

ToBe4minimal

Mitglied
faetzminator hat gesagt.:
Wieso sollte es nicht stimmen, wenn "Eclipse" das ausgibt ???:L ? Da könnte höchstens ein Programmierfehler schuld sein. Um die Rekursion zu verstehen, könntest du einen Parameter für die Rekursionstiefe hinzufügen. Bei jedem Aufruf von f() erhöhst du diesen einfach um 1. Beim Betreten der Methode kannst du Anzahl Leerzeichen = Tiefe * 2 und danach die beiden Parameter übergeben. Beispiel, wir haben folgendes (Methode gibt y=x^n zurück, wobei y>=2000):
Java: 
public static int f(int x) {
    if (x < 2000) {
        return f(x * x);
    }
    return x;
}
Java: 
public static int f(int x, int level) {
    for (int i = 0; i < level; i++) {
        System.out.print("  ");
    }
    System.out.println("f(" + x + ")");
    if (x < 2000) {
        return f(x * x, level + 1);
    }
    return x;
}
Wenn wir nun [c]f(7, 0)[/c] aufrufen, kriegen wir folgende Ausgabe:
Code: 
f(7)
  f(49)
    f(2401)
Zum Vergrößern anklicken....


OK. Dem kann ich soweit auch folgen, aber irgendwie weiß ich trotzdem nicht wie ich bei meiner Aufgabe auf die 10 kommen soll. Entweder ich steh total aufm Schlauch, oder die Rekursion ist so schriftlich über ein Forum einfach zu schwer zu erklären...
 
faetzminator

faetzminator

Gesperrter Benutzer
Wir sind hier, um den Fragestellern eine Hilfe zu sein. Wir sind nicht hier, um möglichst viele Danke's zu erhalten. Wie ich das sehe, verteilt momentan vielleicht jeder 2. User Danke's.
Die Danke-Funktion sollte auch keinen Schwanzvergleich darstellen, sondern lediglich trägt lediglich dazu bei, die Erfahrung eines Benutzers (bei einem Post) etwas einschätzen zu können. Ansonsten ist es gerade für Anfänger schwieriger zu entscheiden, wie viel Gewicht man einer Antwort geben will.
Auf alle Fälle: die einen tun's - die anderen nicht :)
 

Aktuelle Jobs

Neue Themen


Oben