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.