Frage von Lupars, 75

Rekursion effizienter machen?

Moinsen,

ich muss/möchte/würde gerne die Fibonacci-Zahlen rekursiv berechnen lassen. Da aber durch die Rekursion einige Berechnungen mehrmals durchgeführt werden, würde ich gerne wissen, wie man diese Rekursion "effizienter" machen kann. Meine Überlegung war, dass ich mit prev und preprev Variablen arbeite, da scheiterts aber schon an der Berechnung....

Bisher sieht der Code was die Rekursion angeht folgendermaßen aus.

fibRek(int n){ if(n==0){ return 0; }

else if(n==1){

 return 1; 

}else{

 return fibRek(n-1)+fibRek(n-2);

 }

 }

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von KnusperPudding, Community-Experte für Java, 50

Meiner Meinung nach würde ich daran nichts mehr ändern.. wenn du hier mit Previous-Werten, etc. arbeiten willst, bringt dich das nur in Teufels Küche.

Zwar nutze ich das auch gelegentlich bei rekursiven Funktionen, jedoch für dieses Aufgabe würde ich es sein lassen.

Die Fibonacci-Zahlen-Funktion ist mit der Ursprünglichen Formel so schon optimal umgesetzt. 

Kommentar von KnusperPudding ,

Es gibt natürlich noch eine Möglichkeit das zu Lösen, jedoch komplett ohne Rekursion. Was durchaus schneller sein kann.

Ich will mich nicht mit fremden Federn schmücken, daher verweise ich direkt auf die Quelle:

http://www.brpreiss.com/books/opus5/html/page75.html

Sofern du allerdings eine Rekursion erzwingen willst, bist du mit der originalen Methode am besten dran.

Kommentar von Lupars ,

Problematik ist/wahr, das ich eine Lösung finden sollte, in der der Rekursive Fibonacci nicht mehrmals das gleiche rechnet (Siehe Fibonacci-Baumdiagramm o.ä.)
Gelöst habe ich das nun mit einer Methode, welche 3 Übergabeparameter hat, und sich selbst aufruft. Übergabeparameter sind prev, preprev und k, mit denen ich die methode wieder aufrufe

Hier im meinem Beispiel ist Tmp = Temp, also mein kleiner Zwischenspeicher - wie auch immer man es nennen mag. In dieser wird das vorherige prev gespeichert.
Frage ist nun: Ist es nun richtig? Also handelt es sich um eine Rekursion? Die bisherigen Rekursionen die ich gebastelt hatte, sahen alle anders aus.

return RekFiboTimeless((prev+preprev), tmp, n-1); 
Kommentar von KnusperPudding ,

Also erstmal ein Lob, dass du selbst zu einer Lösung gekommen bist und schon mal vorweg: Ich bin kein Mathe Profi oder etwas dergleichen. - Allerdings befasse ich mich relativ intensiv mit java und um einige Probleme zu Lösen greife ich auch gerne auf Rekursion zurück. 

Für mein Verständnis (Da ich in Mathe nie Rekursion als Thema hatte): Eine Rekursive Methode ist eine Methode die sich selbst aufruft, und zwar solange es nötig ist um ein Ergebnis zu erzielen. Meiner Meinung nach ist daher auch eine Methode die Objekt als Zwischenspeicher nutzt, daher immer noch rekursiv. - Leider kann ich das nicht so gut beurteilen da mir der Rest vom Code fehlen würde, was die Effizienz betrifft.

Kommentar von Lupars ,

Schicke dir mal die komplette Methode, davor sind eher unwichtigere Dinge die man noch verbessern sollte.



public double RekFiboTimeless(double prev, double preprev, double n){ if(n == 0){ return prev; }else{ tmp = prev; return RekFiboTimeless((prev+preprev), tmp, n-1); } }
Kommentar von KnusperPudding ,

also es handelt sich immer noch um eine Rekursion meiner Meinung nach. Mir sieht es so aus als sei dein "tmp" eine Klassen- oder Instanzvariable. auch wenn das nicht sonderlich schön ist, handelt es sich stets noch um eine Rekursion. Wobei die Verwendung von Klassen-Instanzvariablen hier meiner Meinung nach nicht zu empfehlen sind. 

Ich würde daher diese durch ein Datenhaltungsobjekt ersetzen, z.B.

private static class Temp {
   public long tmp;

   public Temp(long tmp) {
       this.tmp = tmp;
   }
}

Diesen kannst du im Anschluss als weiteren Parameter an deine Methode anhängen:

private static long RekFiboTimeless(long prev, long preprev, long n, Temp tmp) {
    ...
}
Kommentar von Lupars ,

ich habe das tmp letztendlich rausgenonmmen, indem ich als Methodenaufruf RekFiboTimeless(prev+preprev, prev, k-1) verwende - hätte nicht gedacht das es auch so funktioniert :)
Ich bedanke mich aufjedenfall bei dir :)

Kommentar von KnusperPudding ,

Freut mich wenn ich helfen konnte. Und super dass es geklappt hat.

Antwort
von sarahj, 9

Es gibt noch eine weitere Möglichkeit: memoisation (siehe auch "dynamic Programming").

Im einfachsten Fall merkt man sich Teilergebnisse (z.B. in einer HashTable) und liefert die zurück. Diese Strategie funktioniert übrigens bei vielen Problemen (insbes. Optimierungen).

function fibMemoHelper(n, h) {
    int knownResultOrNull;
    int computedResult;

    if (n <= 1) return n;

    knownResultOrNull = h[n];
    if (knownResultOrNull != NULL) return knownResultOrNull;
    computedResult = fibMemoHelper(n-2, h) + fibMemoHelper(n-1, h);
    h[n] = computedResult;
    return computedResult;
}

function fibMemo(n) {
    return fibMemoHelper(n , new HashTable());
}


In manchen Programmiersprachen (Scheme, Smalltalk, Lisp, Javascript usw.) kann man sogar eine Funktion schreiben, die automatisch eine andere Funktion so "wrappt", daß sie memoised wird.
Z.B. in Scheme:

(define (memoized func)
; returns a memoising wrapper function for func
  (let ((oldFunc func)
        (cache (make-hash-table eq?)))
    (lambda (arg)
      (let ((cacheValue (hash-table-ref/default cache arg #void)))
     (if (void? cacheValue)
        (begin
          (let ((value (oldFunc arg)))
            (hash-table-set! cache arg value)
              value))
          cacheValue)))))

(define (fib n)
  (if (eq? n 1)
    1
    (+
(fib (- n 2))
(fib (- n 1)))))

(define fib (memoize fib))
(fib 1000)
Antwort
von TeeTier, 29

Ohne Rekursion, und sogar ohne Schleifen:

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

double s5, s53, s53s5, s53a5, s53s3h, s53a3h;

size_t fib(unsigned long n) {
--n;

return (size_t)(
s53s5 * pow(s53s3h, n) +
s53a5 * pow(s53a3h, n)
) / 10;
}

int main(void) {
s5 = sqrt(5.0);
s53 = s5 * 3.0;

s53s5 = 5.0 - s53;
s53a5 = 5.0 + s53;

s53s3h = ((3.0 - s5) / 2.0);
s53a3h = ((3.0 + s5) / 2.0);

for (size_t i = 1; i <= 32; ++i) {
printf("#%03ld: %ld\n", i, fib(i));
}

return EXIT_SUCCESS;
}

Die vielen globalen Variablen sind äußerst unschön, aber bei so einem kleinen Snippet wohl zu verschmerzen.

Ich hab das ganze mal grob nach Gefühl anhand der Formeln in der Wikipedia implementiert. Die Mathematik dahinter findest du ebenfalls dort, falls dich das interessiert. :)

Kommentar von TeeTier ,

PS: Ich sehe gerade, dass es unter dem Link aus dem Kommentar von "KnusperPudding" noch weitere interessante Formeln gibt, die du auch mal ausprobieren könntest. Welche davon am effizientesten ist, müsste man sehen.

Aber da selbst der Wertebereich von "unsigned long" relativ klein ist, werden all diese Formeln wenig heraus holen können, da eine Schleife bei so wenigen Iterationen immer schneller sein wird.

Gerade die sqrt() und pow() Funktionen sind verhältnismäßig langsam, wobei ich in meinem Code zumindest alle nötigen Wurzelterme zwischen gespeichert habe (deshalb die globalen Variablen ... wie gesagt unschön, aber effizient).

Antwort
von sarahj, 38

für große Zahlen hat Knuth noch was zu bieten:
Fib(n+m) = Fib(m) * Fib(n+1) + Fib(m-1) * Fib(n)

lohnt aber erst für sehr große n (>10000 oder so).

Keine passende Antwort gefunden?

Fragen Sie die Community