# Fibonacci Folge



## JavaStud20 (21. Mai 2021)

Hallo,

ich muss eine Aufgabe machen bei der ich die Fibonacci-Folge rekursiv berechne und dabei die Aufrufe von Fi unter der Verwendung vom Array h mitzähle. die rekursive Berechnung funktioniert nur das mit dem mitzählen bekomme ich nicht hin. 


```
public static BigInteger fiboRekursiv(int number, int[] h) { //??
        if(number == 0)
            return 0;
        if(number == 1)
            return 1;
        
        BigInteger erg = fiboRekursiv(number-1, h) + fiboRekursiv(number-2, h);
        return erg;
        }
    
    private static void haeufigkeitAusgeben(String[] s, int[] h) {
        BarChartUtil.show("Häufigkeit", "n", "Häufigkeit", Arrays.asList(s), toList(h));
    }
    
    public static void main(String[] args) {
        int[] h //??
        fiboRekursiv(N, h);
        String[] label = new String[h.length];
        for(int i = 0; i < label.length; i++) {
            label[i] = "" + i;
        }
        haeufigkeitAusgeben(label, h);
    }
}
```


----------



## berndoa (21. Mai 2021)

irgendwie... kapiere ich gerade nicht ganz was du machen willst. ne fibonaccizahl berechnen ist klar.
aber was meinst du da nun genau mit dem Array, willst du bspw wenn du eine fibonaccizahl wie 5 bestimmen lässt von deiner methode, mitzählen wo oft die funktion aufgerufen wurde?


----------



## JavaStud20 (21. Mai 2021)

Ja genau.


berndoa hat gesagt.:


> irgendwie... kapiere ich gerade nicht ganz was du machen willst. ne fibonaccizahl berechnen ist klar.
> aber was meinst du da nun genau mit dem Array, willst du bspw wenn du eine fibonaccizahl wie 5 bestimmen lässt von deiner methode, mitzählen wo oft die funktion aufgerufen wurde?


----------



## berndoa (21. Mai 2021)

was ich michg erade generell frage , nur so zur vorgehensweise:
du wirfst da ne zahl, bspw. 5 rein.
dann soll dir da die 5. fibonaccizahl berechnet werden sowie angegeben werden wie viele funktionsaufrufe hierfür nötg sind?


----------



## kneitzel (21. Mai 2021)

Also vermutlich willst Du mitzählen, wie oft für jede einzelne Zahl fiboRekursiv aufgerufen wurde.

Da muss man sich erst einmal überlegen, was denn da aufgerufen wird. Wenn Du fiboRekursiv von 3 aufrufst, was für Aufrufe bekommst Du dann?
Für 3 -> 2 und 1 -> 1 und 0. Also 0...3 muss das Array unterstützen.  Das wäre also eine Länge von n+1.

Und dann kannst Du direkt am Start der Methode das nte Element um 1 hoch zählen.


----------



## kneitzel (21. Mai 2021)

berndoa hat gesagt.:


> was ich michg erade generell frage , nur so zur vorgehensweise:
> du wirfst da ne zahl, bspw. 5 rein.
> dann soll dir da die 5. fibonaccizahl berechnet werden sowie angegeben werden wie viele funktionsaufrufe hierfür nötg sind?


Ja, spiel es doch einmal durch. Oder schreib einfach mal in der Methode etwas raus, also ein einfaches
`System.out.println("Aufruf mit " + number);`
direkt als erste Anweisung in der Methode. Das sollte dann das Verständnis bringen.


----------



## JavaStud20 (21. Mai 2021)

In der Aufgabenstellung steht, dass die Fibonacci-Folge rekursiv berechnet werden soll und die Anzahl der Aufrufe ohne Caching verfolgt werden soll. Also glaube ich mal ja


----------



## berndoa (21. Mai 2021)

kneitzel hat gesagt.:


> Ja, spiel es doch einmal durch. Oder schreib einfach mal in der Methode etwas raus, also ein einfaches
> `System.out.println("Aufruf mit " + number);`
> direkt als erste Anweisung in der Methode. Das sollte dann das Verständnis bringen.


womit ich eher gerade hadere, ist folgendes:
wenn er die fibonaccizahl bestimmen will, wirfst er bspw. i=3 rein, will also die 3. fibonaccizahl.
und rauskommen sollen im endeffekt 2 werte, nämlich die gesuchte fibonacci zahl UND wie viele funktionsaufrufe nötig waren.
da bekanntermassen java als rückgabetyp aber nur eine sache zulässt, müsste man vermutlich mit einem array oder so arbeiten.

ich gehe ja mal nicht davon aus dass die aufgabe damit zu lösen ist dass man sich mathematisch einfach eine explizite formel für die nötige rekursionstiefe herleitet, sondern da shcon rekursiv "mitgezählt" werden soll oder so


----------



## kneitzel (21. Mai 2021)

Nein, der zweite Parameter (h) ist das Array, das die Aufrufe speichern soll. Da das Array ein Referenz-Typ ist, kannst Du die Inhalte verändern und es ist auch außerhalb des Arrays sichtbar. Du kannst nur kein neues Array zuweisen.

Somit ist der Part bereits in dem Code enthalten.


----------



## JavaStud20 (21. Mai 2021)

Und wie soll ich jetzt weiter verfahren? Stehe echt auf dem Schlauch 😅😅


----------



## kneitzel (21. Mai 2021)

```
int[] h //??
```

Hier musst Du ein Array mit der richtigen Größe erstellen. (ein Hinweis habe ich ja in meiner ersten Antwort gegeben).


```
public static BigInteger fiboRekursiv(int number, int[] h) {
    
     //??
    
     if(number == 0)
```

Ich habe den Kommentar noch verschoben - da musst du dann etwas mit dem Array h machen.

Wenn man `h[i]` als Anzahl der Aufrufe mit number = i interpretiert: Was ist dann anzupassen?


----------



## berndoa (21. Mai 2021)

kneitzel hat gesagt.:


> Nein, der zweite Parameter (h) ist das Array, das die Aufrufe speichern soll. Da das Array ein Referenz-Typ ist, kannst Du die Inhalte verändern und es ist auch außerhalb des Arrays sichtbar. Du kannst nur kein neues Array zuweisen.
> 
> Somit ist der Part bereits in dem Code enthalten.


okay, ich steig hier geistig aus. mir will einfach nicht einleuchten wozu das array da sein soll bzw. was hier gewollt ist


----------



## JavaStud20 (21. Mai 2021)

```
for(int i = 0; i <= number; i++) {
    h[i] ++;
}
```

??


----------



## kneitzel (21. Mai 2021)

Der Name h ist natürlich extrem schlecht vorgegeben worden. Ein name wie counter oder so wäre deutlich besser ....

Schau Dir einfach einmal folgendes Beispiel an:

```
public static void f(int x, int[] results) {
    results[x] ++;
}

public static void main(String[] args) {
    int[] results = new int[1];
    System.out.println(results[0]);   
    f(0, results);
    System.out.println(results[0]);   
}
```

Ich hoffe, dass ich da jetzt im Forum kein Tippfehler drin habe ... aber es sollte deutlich werden, was passiert:
- ein int Array wird erzeugt (Größe 1 reicht hier)
- Das erste Element wird ausgegeben. (0)
- Nun wird f aufgerufen um das erste Element zu verändern
- Das erste Element wird erneut ausgegeben....


----------



## kneitzel (21. Mai 2021)

JavaStud20 hat gesagt.:


> ```
> for(int i = 0; i <= number; i++)
> ```
> 
> ??


Wenn der Code ein Ansatz sein sollte für die notwendige Ergänzung in fiboRekursiv, dann ist der Ansatz schon falsch. Es wird keinerlei Schleife benötigt.


----------



## JavaStud20 (21. Mai 2021)

Oh ok. Außerdem steht der Fehler: Type mismatch: cannot convert from int to BigInteger. Wie kann ich diesen beheben? 


kneitzel hat gesagt.:


> Wenn der Code ein Ansatz sein sollte für die notwendige Ergänzung in fiboRekursiv, dann ist der Ansatz schon falsch. Es wird keinerlei Schleife benötigt.


----------



## JavaStud20 (21. Mai 2021)

Wenn ich h[ i ]_++; in die Methode schreiben, muss ich dann nicht noch i initialisieren?_


----------



## berndoa (21. Mai 2021)

kneitzel hat gesagt.:


> Der Name h ist natürlich extrem schlecht vorgegeben worden. Ein name wie counter oder so wäre deutlich besser ....
> 
> Schau Dir einfach einmal folgendes Beispiel an:
> 
> ...


yo, du erhöhst das x'te element um eins. und nu?


----------



## kneitzel (21. Mai 2021)

Wenn fiboRekursiv(5, h) aufgerufen wird: Welches Element von h soll denn dann um 1 erhöht werden?
Das auf fiboRekursiv(number, h) übertragen: Welches Element soll um 1 erhöht werden?



JavaStud20 hat gesagt.:


> Oh ok. Außerdem steht der Fehler: Type mismatch: cannot convert from int to BigInteger. Wie kann ich diesen beheben?


Das ist ein Fehler vom vorgegebenen Code. fiboRekrusiv gibt ein BigInteger zurück und daher gehen gewisse Dinge nicht:
- return 0; bzw. return 1; Hier muss statt einem int ein BigInteger zurück gegeben werden. Also BigInteger.ZERO z.B. oder man nutzt BigInteger.valueOf(...)
- Die Addition geht auch nicht. Operator Overloading hat Java nicht, daher muss hier die add Methode verwendet werden.


----------



## kneitzel (21. Mai 2021)

berndoa hat gesagt.:


> yo, du erhöhst das x'te element um eins. und nu?


Genau, und das ist dann auch außerhalb der Methode sichtbar.

Und nichts anderes wollen wir doch bei fiboRekursiv auch nicht machen. Wir wollen das Element "number" um ein erhöhen, damit wir dann am Ende des rekursiven Laufes wissen, wie oft eine spezifische Zahl als Number aufgerufen wurde.


----------

