Fibonacci-Zahlen

Fibonacci-Zahlen rekursiv und iterativ brechnen.

    #include<iostream>
    using namespace std;

    int fibIter(int);
    int fibRec(int);

    int main()
    {
      cout<<"Bitte eine Zahl eingeben: ";
      int zahl;
      cin>>zahl;
      cout<<"Das Ergebnis ist "<<fibRec(zahl)<<"(rekursiv) und "<<fibIter(zahl)<<"(iterativ)\n";
    }

    int fibIter(int num)
    {
      int result=1;
      int a=1;
      int b=1;

      for(int i=3; i<=num; ++i)
      {
          result=a+b;
          a=b;
          b=result;
      }
      return result;
    }

    int fibRec(int num)
    {
      if(num<=2)
          return 1;
      return fibRec(num-1) + fibRec(num-2);
    }

Wie man sieht ist die iterative Version zwar schneller, aber die rekursive wesentlich einfacher zu schreiben.

Mittels Memoization lässt sich die Rekursion sehr verschnellern. Memoization bedeutet: wir speichern die breits berechneten Werte, zB in einem Array. Denn wenn wir fib(10) berechnen, dann brauchen wir die Werte für fib(9) und fib(8) - allerdings ist fib(8) dann ja schon einmal berechnet worden (von fib(9)):


    int array[500]={0};

    int fibRec(int num)
    {
      if(num<=2)
        return 1;
      if(num<500)
      {
        if(array[num]==0)
        {
          array[num]=fibRec(num-1) + fibRec(num-2);
        }
        return array[num];
      }
      return fibRec(num-1) + fibRec(num-2);
    }

Diese Version ist natürlich wesentlich schneller, da keine Werte mehr als einmal berechnet werden.

top