# Rekursion



## java1986 (22. Jan 2015)

Hallo,
ich hab ein Problem. Ich hab hier ein Aufgabe und hab keine Ahnung, wie ich da rangehen soll :noe:

Aufgabe:

Gegeben sei die folgende Java-Methode.

```
int f (int [] a, int l, int r, int x, int y) {
if (l > r) {
return 0;
}
else{
int m = (l+r)/2;
int f1 = f(a,l,m-1,x,y) + f(a,m+1,r,x,y);
if (x <= a[m] && a[m] <= y) {
return f1 + 1;
}
else {
return f1;
}
}
}
```

a) Stellen Sie die Aufrufstruktur des Aufrufs f(a,0,9,3,6) dar, wobei das Array 
int [] a mit den Werten {8,1,2,4,5,7,8,3,0,7} gegeben sei. 
Tragen Sie in den Baum für jeden Aufruf von f auch den jeweiligen Rückgabewert ein.

b) Beschreiben Sie, was die Methode f allgemein leistet.

// Aufgeben Ende

Die Aufrufstruktur bekomm ich hin und wann welches return dran ist auch.
Nur weiß ich nicht was ich rechnen muss, damit ich f1 rausbekomme. 
Eine Antwort zu b) kann ich auch nicht geben. 

Kann mir jemand sagen, wie ich bei so einer Aufgabe am besten vor gehe???? 
Wie kann man ablesen, was die Funktion macht???

Vielen Dank schonmal


----------



## Flown (22. Jan 2015)

Wie schaut dein Aufrufbaum aus? Was hast du da bereits? Poste ihn doch, dann helf ich dir gerne weiter.


----------



## java1986 (23. Jan 2015)

Ich hoffe du kannst es ein bisschen erkennen, wie ich es meine


----------



## Flown (23. Jan 2015)

So was ich dir sagen kann zu deiner ersten Aufgabe ist, dass du jetzt noch deine Variablenwerte (f1 und f1 + 1) durch die richtigen Werte substituieren musst. 

Zu deiner zweiten Aufgabe:

Was denkst du was das Programm macht?


----------



## java1986 (23. Jan 2015)

Das weiß ich schon, dass ich da was anderes hinschreiben musst. Ich kann nur aus dem Programm nicht rauslesen was es macht. 
Ich dachte mir erst, dass es prüft ob die Mitte einer Zahlenfolgt (von l bis r) zwischen den Werten x und y liegt


----------



## Flown (23. Jan 2015)

Ich kann dir sagen, dass das ein rekursive Lösung zum Besuch aller Elemente in deinem Array ist. Diese Struktur kann man verwenden um eine beinäre Suche anzustoßen oder um die Blätter zu besuchen.

Kleiner Tipp: l und r sind der erste Index im Array und r der Letzte.

(PS: Deine Aufrufhierarchie ist falsch! l kann nie negativ werden.)


----------



## java1986 (23. Jan 2015)

Flown hat gesagt.:


> (PS: Deine Aufrufhierarchie ist falsch! l kann nie negativ werden.)



aber wenn m = 0 ist und ich m-1 rechnen muss, dann kommt doch -1 raus!?


----------



## Flown (23. Jan 2015)

Ah my bad! Ich hab mich wirklich verlesen, du hast recht, es ist richtig.


----------



## java1986 (23. Jan 2015)

ich hab aber immer noch nicht verstanden wie ich f1 bzw. f1+1 ausrechne


----------



## Flown (23. Jan 2015)

Was ist die Rekursionsabbruchbedingung?

Welche Prädikate müssen erfüllt werden um f1 +1 zu erhalten?

Welches Prädikat muss erfüllt werden damit f1 zurückgegeben wird?


----------



## java1986 (23. Jan 2015)

Die Abbruchbedingung ist doch wenn (l>r) ist. 

um f1 + 1 zu erhalten muss die Zahl, die an der Stelle a[m] steht zwischen x und y liegen (oder diese selber sein)

und damit f1 wird beim Rest zurückgegeben. Sprich die Zahl an der Stelle a[m] ist kleiner als x oder größer als y


----------



## Flown (23. Jan 2015)

Was zählt also diese Funktion? Du hast es doch in deinem zweiten Absatz selbst gesagt!


----------



## java1986 (23. Jan 2015)

Sie schaut ob die Zahl an der Stelle a[m] größer oder gleich x ist und kleiner oder gleich y.

Ich glaub ich steh auf dem Schlauch


----------



## Flown (23. Jan 2015)

java1986 hat gesagt.:


> um f1 + 1 zu erhalten muss die Zahl, die an der Stelle a[m] steht zwischen x und y liegen (oder diese selber sein)



Also du hast dir die Antwort schon selbst geliefert!


----------



## java1986 (23. Jan 2015)

das versteh ich aber was für eine Zahl ist dann z.B. beim ersten Aufruf f(a,0,9,3,6) das f1??
Ist es dann 3 weil a[m] (5) die dritte Zahl von 3 - 6 ist?


----------



## Flown (23. Jan 2015)

Du hast doch selbst den Baum aufgezeichnet!

Erst expandiert die Rekursion den ganzen Baum und wenn dann die Abbruchbedingung erreicht ist wird der baum von den Blättern aus bis zur Wurzel zurückgerechnet!

Das heißt alle Teilergebnisse kommen bei der Wurzel zurück.

Wenn du dein Programm ausführst, dann sieht man doch was rauskommt oder nicht?


----------



## java1986 (23. Jan 2015)

das schon ja. aber ich muss bei jedem Aufruf von f den jeweiligen Rückgabewert hinschreiben


----------



## Flown (23. Jan 2015)

Schreib mal in deine Zeichnung die Werte rein die du glaubst?


```
int f1 = f(a,l,m-1,x,y) + f(a,m+1,r,x,y);
if (x <= a[m] && a[m] <= y) {
  return f1 + 1;
} else {
  return f1;
}
```

Alle Teilbäume werden addiert.
Wenn das mittlere Element m zwischen x und y liegt +1 zur Summe sonst Summe zurückgeben!


----------



## java1986 (23. Jan 2015)

Anhang anzeigen 7354

ich habs jetzt mal so gedacht.
Ich denke die Funktion zähl wie viele Zahlen es in einer Zahlenfolge gibt die zwischen 3 und 6 liegen oder selber 3 und 6 sind


----------



## Flown (23. Jan 2015)

Ja es zählt die Zahlen 3 <= a[...] <= 6.

Also kann nur bei dem Array das gegeben ist 3 rauskommen!


----------



## java1986 (23. Jan 2015)

ja ich seh gerade, dass sich in meiner Zeichnung ein Fehler eingeschlichen hat


----------



## java1986 (23. Jan 2015)

Anhang anzeigen 7355

so müsste der Baum dann stimmen oder?


----------



## Flown (23. Jan 2015)

Ehrlich gesagt werd ich es mir nicht ansehen. Da es deine Hausaufgabe ist und du es verstehen musst. Aber in etwa sollte es hinkommen.


----------



## java1986 (23. Jan 2015)

Es sind keine Hausaufgaben. Ich lerne gerade für die Prüfung. Aber trotzdem danke. Du hast mir heute ganz schön weiter geholfen.


----------

