Fibonacci Rekursiv

  • Fibonacci Rekursiv

    Morgen!

    Ich möchte über eine rekursive Funktion calculateFibonacciByCount die Zahl errechnen, die an derjenigen Stelle in der Fibonacci-Folge steht.

    MAFibonacci.h

    Quellcode

    1. #import <Cocoa/Cocoa.h>
    3. @interface MAFibonacci : NSObject {
    4. IBOutlet id textFieldCount;
    5. IBOutlet id textFieldNumber;
    6. int inBetweenValue;
    7. }
    8. - (IBAction)enterPressed:(id)sender;
    9. - (int)calculateFibonacciByCount:(int)count;
    10. @end


    MAFibonacci.m

    Quellcode

    1. #import "MAFibonacci.h"
    3. @implementation MAFibonacci
    4. - (IBAction)enterPressed:(id)sender {
    5. inBetweenValue=0;
    6. [textFieldNumber setIntValue:[self calculateFibonacciByCount:[textFieldCount intValue]]];
    7. }
    9. - (int)calculateFibonacciByCount:(int)count {
    10. if (count==0) {
    11. return 0;
    12. }
    13. else if (count==1) {
    14. return 1;
    15. }
    16. else {
    17. inBetweenValue=inBetweenValue+[self calculateFibonacciByCount:(count-1)];
    18. return inBetweenValue;
    19. }
    20. }
    22. @end
    Alles anzeigen


    textFieldCount liefert die Stelle, dessen Wert berechnet werden soll, als integer an, im textFieldNumber soll dieser ausgegeben werden.

    Problem jetzt nur, dass ich immer 1 als Ergebnis bekomme, was ich auch eingebe.

    Prügelt mich tot ob des wahrscheinlich einfachen Fehlers, ich finde ihn aber nicht :sick:

    MfG
    Alves

  • Original von wolf_10de
    Müsste irgendwie so fuktionieren (nicht getestet)

    Quellcode

    1. int fibonacci(int number)
    2. {
    3. if(number <=2)
    4. return 1;
    5. return fibonacci(number-1) + fibonacci(number-2);
    6. }


    Wenn number == 0, muss aber 0 zurückkommen. 1 nur, wenn number == 1, ansonsten stimmt's.

  • Original von meier
    Original von wolf_10de
    Müsste irgendwie so fuktionieren (nicht getestet)

    Quellcode

    1. int fibonacci(int number)
    2. {
    3. if(number <=2)
    4. return 1;
    5. return fibonacci(number-1) + fibonacci(number-2);
    6. }


    Wenn number == 0, muss aber 0 zurückkommen. 1 nur, wenn number == 1, ansonsten stimmt's.


    na also, dass sollte ja dann kein Problem mehr sein

  • Original von meier
    Original von wolf_10de
    Müsste irgendwie so fuktionieren (nicht getestet)

    Quellcode

    1. int fibonacci(int number)
    2. {
    3. if(number <=2)
    4. return 1;
    5. return fibonacci(number-1) + fibonacci(number-2);
    6. }


    Wenn number == 0, muss aber 0 zurückkommen. 1 nur, wenn number == 1, ansonsten stimmt's.


    dann eben "return number" anstelle von "return 1"

  • RE: Fibonacci Rekursiv

    Original von Alves
    Problem jetzt nur, dass ich immer 1 als Ergebnis bekomme, was ich auch eingebe.

    Prügelt mich tot ob des wahrscheinlich einfachen Fehlers, ich finde ihn aber nicht :sick:

    Manchmal sieht man den Wald vor lauter Bäume nicht. Ich glaube das war auch dein Problem. ;) Ein kurzer Blick auf deine Funktion genügt nämlich, um zu sehen, dass das Ergebnis immer 1 sein muss. :)

  • Original von Alves
    Ich sehe, dass es mit der globalen Var inBetweenValue Probleme gibt, aber wieso ist es so eindeutig, dass es 1 ergibt?

    ich war mir eigentlich ziemlich sicher, dass es funktioniert. Bitte um Aufklärung =)

    Cih würde auch nicht sagen, dass das eindeutig ist. Ich würde sogar sagen, dass es vom verwendeten Compiler anhängt. Du hast dir da nämlich einen fulminaten Seiteneffekt heringefrickelt.

    Also, falls der Compiler inBetweenValue abholt, bevor er die Rekursion ausführt, dann passiert Folgendes:

    inBetweenValue = 0;
    count = 3

    rein in das else
    inBetweenValue wird abgeholt und in ein Register gestopft.
    Jetzt läuft die Rekursion. Wird jetzt jedesMal inBetweenValue vor dem Rekursionseintritt abgeholt, so ist und bleibt es null. Ein späteres Setzen ist unerheblich. Letztlich landet der Wert aus dem count == 1 als Rückgabewert durch alle Rekursionen, was mit der 0 von ganz am Anfang zu 1 addiert wird.

    IIRC ist der Compiler beim+-Operator allerdings berechtigt, die Auswertung so vorzunehmen, wie gerade seine Eier schaukeln. Reihenfolgeregeln existieren IIRC nämlich nur für || und &&.

    Die Ungereimtheiten derlei Seiteneffekte lassen sich übrigens ganz einfach demonstrieren:

    int value = 1;
    NSLog( @"%d %d %d %d %d", ++value, ++value, ++value, ++value, ++value );

    Viel Freude …
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

  • Original von Alves
    Ich sehe, dass es mit der globalen Var inBetweenValue Probleme gibt, aber wieso ist es so eindeutig, dass es 1 ergibt?

    ich war mir eigentlich ziemlich sicher, dass es funktioniert. Bitte um Aufklärung =)

    Deine Variable inBetweenValue ist ja am Anfang 0.

    So nun rufs du deine Funktion calculateFibonacciByCount auf, sagen wir mal mit count=3.
    da count weder 0 noch 1 ist, wird calculateFibonacciByCount mit count=2 aufgerufen.
    count ist also wieder weder 0 noch 1, also wird calculateFibonacciByCount mit count-1, d.h. mit count=1 aufgerufen. Folglich wird die globale Variable inBetweenValue auf 1 gesetzt, da inBetweenValue=inBetweenValue+[self calculateFibonacciByCount:(count-1)]; [0+1=1]

    Die gleiche Erklärung und das gleiche Ergebnis für jeglichen Wert für count der >= 1 ist.

    Vom mathematischen/logischen Standpunkt her finde ich das Resultat also eindeutig.

  • Original von TerminalX
    Original von Alves
    Ich sehe, dass es mit der globalen Var inBetweenValue Probleme gibt, aber wieso ist es so eindeutig, dass es 1 ergibt?

    ich war mir eigentlich ziemlich sicher, dass es funktioniert. Bitte um Aufklärung =)

    Deine Variable inBetweenValue ist ja am Anfang 0.

    So nun rufs du deine Funktion calculateFibonacciByCount auf, sagen wir mal mit count=3.
    da count weder 0 noch 1 ist, wird calculateFibonacciByCount mit count=2 aufgerufen.
    count ist also wieder weder 0 noch 1, also wird calculateFibonacciByCount mit count-1, d.h. mit count=1 aufgerufen. Folglich wird die globale Variable inBetweenValue auf 1 gesetzt, da inBetweenValue=inBetweenValue+[self calculateFibonacciByCount:(count-1)]; [0+1=1]

    Und vor dem nächsten Rekursionsausgang auf 2. Und vor dem nächsten auf 3, … Es wird ja count-2 Mal erhöht

    Original von TerminalX
    Die gleiche Erklärung und das gleiche Ergebnis für jeglichen Wert für count der >= 1 ist.

    Vom mathematischen/logischen Standpunkt her finde ich das Resultat also eindeutig.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?

  • Original von Alves
    Aber dann wird doch eine Stufe höher gegangen, und 1+1 gerechnet und das wiederum in inBetweenValue gespeichert, der dann 2 wird.

    So war es jedenfalls gedacht.

    Hm... okey ich verstehe was du meinst und logisch ist dein Gedanke ebenfalls. Scheint wohl dann wirklich eine Compilersache zu sein. Nämlich geht der nicht, wie du es gerne hättest, zuerst bis zum Schluss und arbeitet sich dann nach oben sondern er ersetzt schon das, was er weiß. (Bildlich jetzt dargestellt) Er weiß, dass inBetweenValue 0 ist, also macht er 0+calculateFibonacciByCount(3-1) und ersetzt somit bei den einzelnen Stufen, die Variable inBetweenValue nicht mit dem veränderten Wert. Somit wird das Resultat zum Schluss auch 1. Aber das heißt ja in anderen Worten, dass der Compiler nur eine halbe Rekursivität vollzieht?...
    Habs gerade mal mit Perl probiert. Da wirds "richtig" gemacht, obwohl der Algorithmus für die Fibonacci-Folge immer noch falsch ist. ;) Das was du hinbekommen hast ist eine umständliche Methode für 2 hoch (count-2) zu rechnen. :)

  • Manche Programmiersprachen legen die Auswertereihenfolge fest. Da kann man sich auf so etwas verlassen. In C ist das IIRC nur für && und || der Fall, weil das wichtig für Pointerbritzeleien ist:

    if( attrib && [attrib isEqualToString:@"Amin"] )

    Aber insgesamt sollte man gänzlich die Finger von globalen Variablen lassen und erst recht in Rekursionen. Das führt zu nichts Gutem.
    Es hat noch nie etwas gefunzt. To tear down the Wall would be a Werror!
    25.06.2016: [Swift] gehört zu meinen *Favorite Tags* auf SO. In welcher Bedeutung von "favorite"?