# Rekursiver Algorithmus



## ToBe4minimal (22. Jun 2010)

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


----------



## Marco13 (22. Jun 2010)

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...  )

```
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 (22. Jun 2010)

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


```
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:


```
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.


----------



## ToBe4minimal (22. Jun 2010)

OK.

Und was kommt dann bei meiner Aufgabe raus??

Ich versteh nicht wie das dann in meinem Fall am Ende zusammen gerechnet wird.


----------



## Marco13 (22. Jun 2010)

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(...)")


----------



## ToBe4minimal (22. Jun 2010)

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(...)")




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


----------



## ToBe4minimal (22. Jun 2010)

```
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??


----------



## Appleleptiker (22. Jun 2010)

ToBe4minimal hat gesagt.:


> Und wie wird das dann zusammen gerechnet??



Hab's ausgerechnet. Stimmt.
http://dl.dropbox.com/u/1808933/rekusrion.pdf


----------



## faetzminator (23. Jun 2010)

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):

```
public static int f(int x) {
    if (x < 2000) {
        return f(x * x);
    }
    return x;
}
```


```
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:

```
f(7)
  f(49)
    f(2401)
```


----------



## ToBe4minimal (23. Jun 2010)

Appleleptiker hat gesagt.:


> Hab's ausgerechnet. Stimmt.
> http://dl.dropbox.com/u/1808933/rekusrion.pdf




OK. Jetzt wäre noch interessant zu erfahren, wie du das ausgerechnet hast.
Kann mir das nicht mal jemand an meinem Beispiel vorrechnen??


----------



## ToBe4minimal (23. Jun 2010)

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):
> 
> ```
> public static int f(int x) {
> ...




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...


----------



## ToBe4minimal (23. Jun 2010)

Sorry, hab gerade gesehen Appleleptiker hat es ausgerechnet!!

DANKE!!!


----------



## Appleleptiker (23. Jun 2010)

ToBe4minimal hat gesagt.:


> OK. Jetzt wäre noch interessant zu erfahren, wie du das ausgerechnet hast.
> Kann mir das nicht mal jemand an meinem Beispiel vorrechnen??



//EDIT
Hat sich damit ja dann erledigt, hast es ja


----------



## faetzminator (23. Jun 2010)

Appleleptiker hat gesagt.:


> //Edit. Oh verstehstes ja. n Klick auf Danke wär super



Bitte keine Bitten nach "Danke drücken"...


----------



## Appleleptiker (23. Jun 2010)

Versteh zwar nicht warum, aber ich akzeptier's mal so.


----------



## faetzminator (23. Jun 2010)

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


----------

