Fibonacci Rekursiv...

Golfi1812

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

SG1

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 ?

icarus2

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

*Rewind*

icarus2 schrieb:

in konstanter Zeit

Was ist das denn für ein Begriff?

icarus2

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