Rekursion so machbar?

Theophrastus

Hallo zusammen,

ich habe in dem c++ Kurs ein Beispiel zur Rekursion gefunden, bekomme aber bei der Ausführung immer einen Fehler.
Die Funktion:

int fibRek(int n)
{
if(n==1)
return 1;
else if(n==2)
return 1;
else
return fibRek(n-1)+fibRek(n-2);
};

Kann es sein, dass diese Rekursion gar nicht machbar ist, weil die Funktion in einem Aufruf quasi zweimal aufgerufen wird, oder gibt es da noch ein anderes Problem?

Vielen Dank im voraus.

Theo

Bashar

Was für nen Fehler bekommst du denn? Die Funktion ist so korrekt (bis auf das Semikolon nach der schließenden Klammer).

life

das else kannste übrigens überall weglassen..

ness

Zeigmal den ganzen code, wenn man davon absieht, dass es äußerst inperformant ist, ist die Funktion korrekt. btw: BITTE CODETAGS BENUTZEN

Theophrastus

So das ist dann der gesamte code, inklusive der vorgeschlagenen Korrekturen:

#include<iostream>
#include<stdio.h>

using namespace std;
int n;
int ergebnis;

int fibo(int)
{
    if(n == 1)
         return 1;
    if(n == 2)
         return 1;
         return fibo(n-1) + fibo(n-2);
}

int main()
{
    cout<<"Geben Sie eine Zahl ein deren Fibonacci Zahl Sie bestimmen möchten : ";
    cin>>n;

    ergebnis = fibo(n);

    cout<<"Die Fibonaccizahl von "<<n<<" ist "<<ergebnis<<endl;
    getchar();
    return 0;
};

Mit inperformant meinst Du, nehme ich mal an, dass man das schneller oder besser lösen könnte. Mag sein, da ich aber grade erst mit c++ angefangen habe, würde es mir schon helfen, wenn die Sache einfach läuft und ich begreife warum sie läuft bzw. warum dann nicht
Der Fehler den ich bekomme ist eine "unkown software exeption" nach Eingabe der Zahl.

Theo

Bashar

Wieso hast du hier das n im Kopf von fibo weggelassen?? Und bitte pack n und ergebnis in die main, was soll das denn auf Dateiebene? Eigentlich hätt der Compiler dir ja gesagt, dass du das n in fibo vergessen hast, aber dadurch, dass eine globale Variable mit diesem Namen sichtbar war ...

life

außerdem ist die einrückung von "return fibo(n-1) + fibo(n-2);" irreführend

Windalf

int fibo(unsigned int n){return n<3?1:fibo(n-1)+fibo(n-2);}

life

Windalf schrieb:

int fibo(unsigned int n){return n<3?1:fibo(n-1)+fibo(n-2);}

wow 1337 H4X0R!!!

Windalf

wow 1337 H4X0R!!!

Ich würd sagen eher erbärmlich da ich das unsigned auch vorne vergessen habe... size_t sollte besser geeigenet sein und nen lookuptable sollte das ganze wesentlich beschleunigen...

life

ich würd dir mal zu einer iterativen vorgehensweise raten :p

zumal ich nicht weiß warum du size_t benutzen willst oO Aber wenn du schon dabei bist, kannste auch gleich nen paar const dazufügen. Das macht den code blauer Wobei das size_t dann wieder blau wegnimmt

ness

const std::size_t array_size=...;

template<class U>
class l_table    //lästige initialisierungen...
{
private:
    U a[array_size];
public:
    l_table(){for(std::size_t i=0;i<array_size;++i)a[i]=0;a[0]=a[1]=1};
    U& operator[](std::size_t index){if(index>=array_size)return 0;return a[index];};
};

template<class U>
U fibonacci(U ui)
{
    static l_table look;
    if((U& t=l[static_cast<std::size_t>(ui)])!=0)
        return t;
    else
        return t=fibonacci(ui-1)+fibonacci(i-2);
};

Weß au net wieso ich das jetzt hier hingeschrieben hab...
Is auch nicht iterativ, dass kann der threadersteller machen wenn er will...

life

das else ist überflüssig und das if funktioniert so auch nicht.. musste so schreiben:

template<class U> 
U fibonacci(U ui) 
{ 
    static l_table<U> look;
    U& t=look[static_cast<std::size_t>(ui)]);
    if(t) 
        return t;
     return t=fibonacci(ui-1)+fibonacci(ui-2); 
};

außerdem geht dein

U& operator[](std::size_t index){if(index>=array_size)return 0;return a[index];};

so auch nicht, da du nicht die konstante 0 per nicht konstanter referenz übergeben kannst >_<

Wenn du Fibonacci-Zahlen schnell ausrechnen willst, machst dus nicht rekursiv. (Hoffe ich mal...)

Der klassische Fehler bei der Berechnung der Fibonacci-Zahlen

Ich will die Lösung nicht verraten, aber mal als Hinweis:
Jede Fibonacci-Zahl berechnet sich aus der Summe ihrer beiden Vorgänger. Wenn ich nun f(n) = f(n-2) + f(n-1) schreibe, ist es dann wirklich nötig, für f(n-2) und f(n-1) die volle Rekursion durchzugehen?

Ich meine (kann sein, dass ich daneben liege), dass die Komplexität so exponentiell ist. Es geht aber linear.

Jester

Harry Hirsch schrieb:

Ich meine (kann sein, dass ich daneben liege), dass die Komplexität so exponentiell ist.

Da liegst Du richtig. Um so rekursiv fib(n) zu berechnen werden fib(n) (+/- 1) Aufrufe der Funktion durchgeführt. Da die Fibonacci-Zahlen exponentiell wachsen ist auch der Aufwand exponentiell.

Lustigerweise könnte man fib(n) demnach auch berechnen, indem man in einer globalen Variable die Funktionsaufrufe mitzählt.

Theophrastus

Nochmal ich, vielen Dank für die Antworten, auch wenn ich noch nicht alle verstanden habe, ist aber spaßig was sich aus einer Anfängerfrage so alles entwickelt

Theo

ness

life schrieb:

das else ist überflüssig und das if funktioniert so auch nicht.. musste so schreiben:

Das else ist nicht überflüssig, sonst kann man t nicht mehr sehen. Was ist an dem if falsch?

life schrieb:

template<class U> 
U fibonacci(U ui) 
{ 
    static l_table<U> look;
    U& t=look[static_cast<std::size_t>(ui)]);
    if(t) 
        return t;
     return t=fibonacci(ui-1)+fibonacci(ui-2); 
};

außerdem geht dein

U& operator[](std::size_t index){if(index>=array_size)return 0;return a[index];};

so auch nicht, da du nicht die konstante 0 per nicht konstanter referenz übergeben kannst >_<

Da haste mich drangekriegt. Sollte man am besten als membervariable machen und der vor jeder Rückgabe 0 zuweisen. Ist aber nicht sonderlich performant.

Walli

Oder einfach keine Referenz zurückgeben...

7H3 N4C3R

unsigned fibonacci( unsigned i)
{
  if( i == 0) return 0;
  if( i < 3) return 1;
  int n1( 1);
  int n2( 2);
  i -= 3;
  for( ; i != 0; --i) {
    int tmp( n1 + n2);
    n1 = n2;
    n2 = tmp;
  }
  return n2;
}