Fibonacci Rekursiv...



  • Hey C++ler,

    ich habe als kleine Übung ein Programm geschrieben, dass eine Fibonaccische Zahlenfolge erstellt und ausgibt.

    Wie könnte man das Programm rekursiv machen?

    Hier der Code:

    #include "../../../std_lib_facilities.h"
    
    void print(const vector<int>& zahlen) //print () die Folgenglieder aus
    {	
    	int i = 0;
    	while(i<zahlen.size()){
    		cout<<zahlen[i]<<"\n";
            ++i;
    	}
    	keep_window_open();
    }
    
    void fibonacci(int x,int y,int n)
    {
    	vector<int>zahlen;
    	zahlen.push_back(x);
    	zahlen.push_back(y);
    
    	int i = 2;
    	while(zahlen.size()<=n){
    		zahlen.push_back(zahlen[i-2]+zahlen[i-1]); //die beiden vorherigen Zahlen miteinander addieren
    		++i;
    	}
    
    	print(zahlen); //Übergibt Vector an print()
    }
    
    int main(){
        int x = 1; //ertes Folgenglied
    	int y = 2; //zweites Folgenglied
    	int n = 0;
    	cout<<"Definiere n:";
    	cin>>n;
    	fibonacci(x,y,n);  //ruft fibonacci() auf
    }
    


  • Kuck dir mal ein x-belibiges anderes (einfaches) Beispiel für Rekursion an
    und überleg, was du da als Inspiration verwenden kannst.
    Wenn jetzt jemand "so:" sagt, dann bringt es dir nicht wirklich was.
    Dann kannst du ja einen noch nicht funktionsfähigen Ansatz posten, aber ohne Mitarbeit von dir bringt es nix



  • Definition der Fibonacci-Zahlen angucken und einfach abschreiben. Gut, das wird dann füchterlich ineffizient (Bonusfrage: warum?), aber rekursiv.



  • SG1 schrieb:

    Gut, das wird dann füchterlich ineffizient (Bonusfrage: warum?), aber rekursiv.

    Funtioncall-overhead oder worauf willst du hinaus ?



  • cvcv schrieb:

    SG1 schrieb:

    Gut, das wird dann füchterlich ineffizient (Bonusfrage: warum?), aber rekursiv.

    Funtioncall-overhead oder worauf willst du hinaus ?

    Die iterative Variante ist definitiv schneller. Und wenn man bedenkt, dass man Fibonacci in konstanter Zeit berechnen kann...

    Aber als Uebung ists ganz gut geeignet 🙂



  • icarus2 schrieb:

    in konstanter Zeit

    Was ist das denn für ein Begriff?



  • [Rewind] schrieb:

    icarus2 schrieb:

    in konstanter Zeit

    Was ist das denn für ein Begriff?

    Hat konstante Lauftzeit <==> in konstanter Zeit

    *Edit
    Ich beziehe mich damit auf die direkte Formel fuer die n-te Fibonacci Zahl.


Log in to reply