Rekursion so machbar?

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;
}

ness

Walli schrieb:

Oder einfach keine Referenz zurückgeben...

ne, dann kann ich ja nicht das array editieren...
@7H3 N4C3R und alle die nach iteration schreien:
klar, is auch ne möglichkeit mehr performance raus zu kitzeln, aber das würde ich definitiv hinter dem lookuptable anordnen.

7H3 N4C3R

Bevor Du anfängst, mir Lookup-Tabellen u.ä. zu hantieren, solltest Du sehen, dass Du den Algorithmus optimierst. Mit der iterativen Version wandelt man ein np-schweres (in nicht polynomialer Zeit lösbares) Problem in ein lineares um. Wer diesen Schritt der Optimierung nicht geht ist selber Schuld.
Zu der Lookup-Tabelle... worst-case optimal betrachtet ändert sie garnichts an der Schwere des Problemes. Bei sehr häufigem Einsatz kann das was bringen, allerdings muss man sie dann schon sehr groß Anlegen, damit sie wirklich etwas bringt.

Soo, jetzt sind wir aber gänzlich am Topic vorbeigeschossen... die Mods mögen uns verzeihen

Walli

ness: Naja, wenn schon LUT dafür, dann würde ich sie mir zur Compilezeit berechnen lassen oder dumm selber runterschreiben. Performanter geht es eigentlich nicht. Aber eigentlich ist es ja nur ne dumme Übung...

ness

Und ich soll mich nicht noch mal rechtfertigen? Dann will ich mal:
Nehmen wir mal an, wir berechnen fib(7). Ohne LUT (ich kappe mal schon bei 2):

fib(7)

fib(6)                                                                                     fib(5)

fib(5)                                                    fib(4)                           fib(4)                        fib(3)

fib(4)                          fib(3)                    fib(3)            fib(2)         fib(3)            fib(2)      fib(2) fib(1)

fib(3)           fib(2)         fib(2) fib(1)             fib(2) fib(1)                    fib(2) fib(1)

fib(2) fib(1)

(Ich hoffe mal das ist verständlich)
Mit LUT:

fib(7)

fib(6)   fib(5)
         /
       /
     /
fib(5)  fib(4)       
         /
       /
     /
fib(4)  fib(3)
         /
       /
     /
fib(3)  fib(2)
         / 
       /   
     /      
fib(2) fib(1)

Die LUT macht also eine ganze Menge Wett, aber ich will nicht bestreiten, dass es nicht sinnvoll ist, eine iterative Variante zu programmieren...
/edit: streng genommen ist meins algorithmus-optimierung. Ich habs umgeformt, so das jetzt ein dynamischer topdown algorithmus ausgeführt wird...