Fibonacci-Zahlen rekursiv berechnen

[DerDecane]

Hey, ich muss als Aufgabe in Java die Berechnung der Fibonacci-Zahlen in Java implementieren. Das ganze Programm soll in der main-Methode stattfinden, das heißt außer der main darf ich keine andere Methode verwenden. Ich soll in der main-Methode einmal die Fibonacci-Zahlen iterativ und einmal rekursiv berechnen. Die iterative Variante hab ich und die funktioniert super und sieht so aus:

int fibonacciIt=0;
int fibonacci1=0;
int fibonacci2=1;

if (n == 0 || n == 1){
    fibonacci1=n;
}
for (int i=0; i<n; i++){
   fibonacciIt=fibonacci1+fibonacci2;
   fibonacci1=fibonacci2;
   fibonacci2=fibonacciIt;
}
System.out.println(fibonacci1);

Allerdings habe ich keine Ahnung wie das rekursiv gemacht werden soll, ohne eine Methode die sich selbst aufrufen kann verwenden zu dürfen.
Jemand eine Idee?

 

[kneitzel]

Also das über die main-Methode zu machen, halte ich für sehr kritisch. Aber sollte gehen, da Du ja dort auch Argumente hast. Das sind zwar Strings, aber ok - int nach string und dann strings wieder parsen - das sollte gehen.
Bleibt das Problem mit dem Rückgabewert - das ist etwas schwerer, aber das könnte man über eine statische Variable lösen, die dann immer gesetzt wird. Da Du nur einen Thread hast, sollte das gehen.

ABER: Sicher, dass Du das nicht falsch verstanden hast? Das ist sehr untypisch als Anforderung.

Konrad

 

[DerDecane]

Ne da steht ausdrücklich, dass die Berechnungen in der main-Methode ausgeführt werden sollen. Deshalb wunderts mich ja selbst und deshalb hab ich auch keine Ahnung. Als eigene Methode wäre das rekursiv ja kein Problem ^^

 

[Joose]

Dann musst du dich an den Aufgabensteller wenden, der kann dir am besten sagen wie du eine Rekursion ohne Methode lösen kannst (er hat sich diese Aufgabe ja auch ausgedacht und hat hoffentlich eine Musterlösung)

 

[DerDecane]

Bei meiner iterativen Lösung verwende ich ja 2 Hilfsvariablen. Kann ich nicht eine oder sogar beide "weglassen" und alles nur mit einer Variable (bzw. einer Variable und einer Hilfsvariable) lösen - vielleicht ist ja das mit rekursiv gemeint, weil die Variable x dann sich selbst mit einer neuen Variable verrechnet. Sprich x+=y oder sowas.

 

[Joose]

Möglicherweise .... in der Programmierung ist mit Rekursion aber meist eine Methode gemeint welche sich selber aufruft (bzw. auch mehrere).

 

[kneitzel]

Also die Frage ist, das Du genau machen musst. Streng genommen brauchst Du keine einzige Variable, denn es gibt eine Formel, um fib(n) zu berechnen. (Etwas sehr kompliziert, aber Mathematiker schaffen sowas halt auch.) Wenn es aber um die Serie geht, dann macht eine komplizierte Berechnung keinen Sinn.

Und Du brauchst 3 Variablen. Du musst ja zwei Vorgänger haben um dann die neue Zahl auszurechnen. Dann musst Du die beiden Vorgänger neu setzen und sobald Du den ersten gesetzt hast, ist die Berechnung nicht mehr möglich. Somit denke ich, dass 3 Variablen wirklich benötigt werden.

Konrad

 

[DerDecane]

Ich kanns mir ehrlichgesagt auch nicht ohne 3 Variablen vorstellen (wenn's nur in der main sein soll). Ich werds jetz mal mit Methoden umsetzen das macht sonst sowieso keinen großen Sinn.

 

[Flown]

Kannst du bitte den genauen Wortlaut der Aufgabe hier posten?

 

[DerDecane]

Schreiben Sie ein Java-Programm welches in der main Methode die Fibonacci-Zahlen auf zwei Arten löst, und zwar sowohl rekursiv als auch iterativ. Dazu soll eine beliebige Eingabe von der Tastatur empfangen und die beiden Ergebnisse auf den Bildschirm ausgegeben werden.

 

[Flown]

Also es ist bestimmt vorgesehen eine Methode für jede Variante zu erstellen, andernfalls ist das ziemlich sinnlos.

 

[DerDecane]

Ja muss wohl so sein, schlechte Wortwahl der Aufgabe.

 

[Xyz1]

Die Fibonacci-Zahlen sind über den rekursiven Bildungssatz definiert, nachzulesen bei Wikipedia, d. h., sie können rekursiv oder iterativ formuliert werden:

/**
 * @author DerWissende
 */
public class Temp {

    public static void main(String[] args) {
        Temp t = new Temp();
        for (int i = 0; i < 10; i++) {
            System.out.printf("%d\t%d\t%d%n", i, t.fib(i), t.fibIter(i));
        }
    }

    long fib(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        return (fib(n - 1) + fib(n - 2));
    }

    long fibIter(int n) {
        long i1 = 0, i2 = 1, temp;
        while (--n > 0) {
            temp = i1 + i2;
            i1 = i2;
            i2 = temp;
        }
        return i2;
    }
}

Ergebnis:

run:
0	0	1
1	1	1
2	1	1
3	2	2
4	3	3
5	5	5
6	8	8
7	13	13
8	21	21
9	34	34
BUILD SUCCESSFUL (total time: 0 seconds)

Jetzt sieht man schnell, dass bis auf 0 0 1 alles stimmt.

 

[Flown]

Für den iterativen Algorithmus eher:

public static int fib(int n) {
	int fibN = 0, fibSucc = 1;
	for (int i = 0; i < n; i++) {
		fibSucc = fibN + (fibN = fibSucc);
	}
	return fibN;
}

 

[Xyz1]

Oder eine kleine Änderung:

    long fibIter(int n) {
        long i1 = 0, i2 = 1, temp;
        while (--n >= 0) {
            temp = i1 + i2;
            i1 = i2;
            i2 = temp;
        }
        return i1;
    }

Dabei ist mir nebenbei Folgendes aufgefallen:

run:
0	0	0
1	1	1
2	1	1
3	2	2
4	3	3
5	5	5
6	8	8
7	13	13
8	21	21
9	34	34
10	55	55
11	89	89
12	144	144
13	233	233
14	377	377
15	610	610
16	987	987
17	1597	1597
18	2584	2584
19	4181	4181
20	6765	6765
21	10946	10946
22	17711	17711
23	28657	28657
24	46368	46368
25	75025	75025
26	121393	121393
27	196418	196418
28	317811	317811
29	514229	514229
30	832040	832040
31	1346269	1346269
32	2178309	2178309
33	3524578	3524578
34	5702887	5702887
35	9227465	9227465
36	14930352	14930352
37	24157817	24157817
38	39088169	39088169
39	63245986	63245986
40	102334155	102334155
41	165580141	165580141
42	267914296	267914296
43	433494437	433494437
44	701408733	701408733
45	1134903170	1134903170
46	1836311903	1836311903
47	2971215073	2971215073
48	4807526976	4807526976
49	7778742049	7778742049
50	12586269025	12586269025
BUILD SUCCESSFUL (total time: 4 minutes 8 seconds)

Ich würde nicht behaupten, mein Rechner sei langsam, also muss die rekursive Methode stinklangsam sein. Klar, kann man sie auch "tunen", aber bei soetwas ist dann die iterative "vorzuziehen".

Grüße

 

[JStein52]

Die Rechenzeit geht bei der rekursiven Lösung offensichtlich nicht linear nach oben. Bei n=43 waren es z.B. 11 sec. und bei n=45 waren es schon 28 sec. Und mit n=50 hatte ich auch die besagten 4 min. Abgesehen von diesem Problem neigen rekursive Lösungen für solche mathematischen Aufgaben auch dazu irgendwann mit Stackoverflow abzuschmieren.

 

[Xyz1]

Für den iterativen Algorithmus eher:

ich will dich keinesfalls kritisieren, aber das versteckt "nur" eine dritte Variable, die intern angelegt wird. und Speicherplatzverhalten ist das O(4) anstatt O(3), imo.

(Etwas sehr kompliziert, aber Mathematiker schaffen sowas halt auch.)

Eigentlich bin ich kein Freund Komplettlösungen von. Aber wenn ich "fibonacci java" eingebe, dann sehe ich ja, dass es kein Staatsgeheimnis ist, z. B. diese Seite: http://java.soeinding.de/content.php/fibonacci

Somit sei mir mein Quelltext verziehen.

Der Beitrag von JStein52 gefällt mir sehr gut.

 

[Flown]

ich will dich keinesfalls kritisieren, aber das versteckt "nur" eine dritte Variable, die intern angelegt wird. und Speicherplatzverhalten ist das O(4) anstatt O(3), imo.

Nö wird keine Variable intern angelegt (es wird wie bei einer Hilfsvariable auf Maschinenebene genau so ein Register benötigt - nur in der JVM sparst du dir einen Platz - aber lädst die Zahlen 2 mal von der selben Stelle)!
Es ging hier auch nie um Speicherkomplexität, wobei hier die Landau-Notation falsch gewählt ist!

 

[JStein52]

Weiter oben wurde allerdings schon mal diskutiert ob man denn nun 2 oder 3 Variablen benötigt. Und da ging es nicht drum ob die intern in Registern oder sonstwo abgelegt werden. Insofern war der Hinweis von @DerWissende schon richtig dass bei dir die dritte Variable nur nicht sichtbar ist.

 

[Flown]

@JStein52, @DerWissende: Es sind genau 4 Variablen im Spiel: n, i, fibN, fibSucc. Nicht mehr! Keine intern abgelegte Variable, wenn so was geben würde, würde es in eine JLS beschrieben sein - auch nachgesehen und nichts gefunden. Wenn es sowas geben würde, dann bitte um einen Nachweis, sonst: Proof or it didn't happened!
Das i könnte man eliminieren und while mit n reduzieren -> Aber ich finde es nicht schön Parameter zu verändern.

 

[Xyz1]

Ob die Variable nun im Register oder Speicher liegt, ist Jacke wie Hose. Sie ist ja da.

O-Notation, anders kann ich es leider bei konstanten Speicherplatzverhalten nicht darstellen, sonst wäre alles O(1).

Also bitte nicht "in's Hemd machen".

Das i könnte man eliminieren und while mit n reduzieren -> Aber ich finde es nicht schön Parameter zu verändern.

Alle "primitiven" werden kopiert, sag ich da nur.

 

[Flown]

• Zeig mal wo denn diese Variable sein soll?

• Konstant bleibt konstant egal welcher Wert.

• Egal ob Kopie oder nicht, bleibt Geschmackssache ob man Parameter ändern will oder nicht.

 

[Flown]

Addendum: Hier mal, wie der Beweis einer Behauptung funktionieren sollte:

package test;

public class Test {
 
    public static void main(String... args) {
        fib(20);
    }
 
    public static int fib(int n) {
        int fibN = 0, fibSucc = 1;
        for (int i = 0; i < n; i++) {
            fibSucc = fibN + (fibN = fibSucc);
        }
        return fibN;
    }
}

Bytecode:

public class test.Test
  minor version: 0
  major version: 52
  flags: ACC_PUBLIC, ACC_SUPER
Constant pool:
   #1 = Methodref          #4.#16         // java/lang/Object."<init>":()V
   #2 = Methodref          #3.#17         // test/Test.fib:(I)I
   #3 = Class              #18            // test/Test
   #4 = Class              #19            // java/lang/Object
   #5 = Utf8               <init>
   #6 = Utf8               ()V
   #7 = Utf8               Code
   #8 = Utf8               LineNumberTable
   #9 = Utf8               main
  #10 = Utf8               ([Ljava/lang/String;)V
  #11 = Utf8               fib
  #12 = Utf8               (I)I
  #13 = Utf8               StackMapTable
  #14 = Utf8               SourceFile
  #15 = Utf8               Test.java
  #16 = NameAndType        #5:#6          // "<init>":()V
  #17 = NameAndType        #11:#12        // fib:(I)I
  #18 = Utf8               test/Test
  #19 = Utf8               java/lang/Object
{
  public test.Test();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 3: 0

  public static void main(java.lang.String...);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC, ACC_VARARGS
    Code:
      stack=1, locals=1, args_size=1
         0: bipush        20
         2: invokestatic  #2                  // Method fib:(I)I
         5: pop
         6: return
      LineNumberTable:
        line 6: 0
        line 7: 6

  public static int fib(int);
    descriptor: (I)I
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=3, locals=4, args_size=1              // <----------------------- total locals (stack + args): n, i, fibSucc, fibN
         0: iconst_0   //load 0
         1: istore_1    //fibN = 0
         2: iconst_1   //load 1
         3: istore_2   //fibSucc = 1
         4: iconst_0   // load 0
         5: istore_3   // i = 0
         6: iload_3    // load i
         7: iload_0    // load n
         8: if_icmpge     23 // i >= n ?
        11: iload_1   // load fibN
        12: iload_2   // load fibSucc
        13: dup         // duplicate top -> fibSucc [Stack: fibN, fibSucc, fibSucc]
        14: istore_1 // fibN = fibSucc [Stack: fibN, fibSucc]
        15: iadd        // fibN + fibSucc [Stack: fibN+fibSucc]
        16: istore_2 // fibSucc = fibN + fibSucc
        17: iinc          3, 1 //i++
        20: goto          6
        23: iload_1 // load fibN
        24: ireturn // return fibN
      LineNumberTable:
        line 10: 0
        line 11: 4
        line 12: 11
        line 11: 17
        line 14: 23
      StackMapTable: number_of_entries = 2
        frame_type = 254 /* append */
          offset_delta = 6
          locals = [ int, int, int ]                 // <--------------------------------- stack locals (frame managed): i, fibN, fibSucc
        frame_type = 250 /* chop */
          offset_delta = 16
}
SourceFile: "Test.java"

So und jetzt noch mal um das Andere zu zeigen:

package test;

public class Test {
  
    public static void main(String... args) {
        fib(20);
    }
  
    public static int fib(int n) {
        int fibN = 0, fibSucc = 1;
        while (0 < n--) {
            fibSucc = fibN + (fibN = fibSucc);
        }
        return fibN;
    }
}

Bytecode (Erklärung schenk ich mir, da ja oben so und so der Ablauf erklärt wird):

public class test.Test
  minor version: 0
  major version: 52
  flags: ACC_PUBLIC, ACC_SUPER
Constant pool:
   #1 = Methodref          #4.#16         // java/lang/Object."<init>":()V
   #2 = Methodref          #3.#17         // test/Test.fib:(I)I
   #3 = Class              #18            // test/Test
   #4 = Class              #19            // java/lang/Object
   #5 = Utf8               <init>
   #6 = Utf8               ()V
   #7 = Utf8               Code
   #8 = Utf8               LineNumberTable
   #9 = Utf8               main
  #10 = Utf8               ([Ljava/lang/String;)V
  #11 = Utf8               fib
  #12 = Utf8               (I)I
  #13 = Utf8               StackMapTable
  #14 = Utf8               SourceFile
  #15 = Utf8               Test.java
  #16 = NameAndType        #5:#6          // "<init>":()V
  #17 = NameAndType        #11:#12        // fib:(I)I
  #18 = Utf8               test/Test
  #19 = Utf8               java/lang/Object
{
  public test.Test();
    descriptor: ()V
    flags: ACC_PUBLIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 3: 0

  public static void main(java.lang.String...);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC, ACC_VARARGS
    Code:
      stack=1, locals=1, args_size=1
         0: bipush        20
         2: invokestatic  #2                  // Method fib:(I)I
         5: pop
         6: return
      LineNumberTable:
        line 6: 0
        line 7: 6

  public static int fib(int);
    descriptor: (I)I
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=3, locals=3, args_size=1  // <----------------------- total locals (stack + args): n, fibSucc, fibN
         0: iconst_0
         1: istore_1
         2: iconst_1
         3: istore_2
         4: iconst_0
         5: iload_0
         6: iinc          0, -1
         9: if_icmpge     21
        12: iload_1
        13: iload_2
        14: dup
        15: istore_1
        16: iadd
        17: istore_2
        18: goto          4
        21: iload_1
        22: ireturn
      LineNumberTable:
        line 10: 0
        line 11: 4
        line 12: 12
        line 14: 21
      StackMapTable: number_of_entries = 2
        frame_type = 253 /* append */
          offset_delta = 4
          locals = [ int, int ]   // <--------------------------------- stack locals (frame managed): fibN, fibSucc
        frame_type = 16 /* same */
}
SourceFile: "Test.java"

Keine versteckten Variablen, also: q.e.d.

Weiters: Verwendung von Methoden-Parameter ist ein code smell in meinen Augen und der Grund ist auch hier zu finden: Assignment to parameters

 

[JStein52]

Ist das jetzt nicht ein bisschen Haarspalterei ? Es ging ja bei den Variablen nie um i oder n !! Wie @kneitzel oben geschrieben hat muss man bei dem Algorithmus 3 Werte irgendwo speichern egal wo und wie trickreich man das hinschreibt. Würdest du dem zustimmen ?

 

[Flown]

Mal vorweg. Ich habe meinen Code nicht gepostet, um zu zeigen wie man Variablen spart, sondern einfach weil der iterative Algorithmus HIER einfach falsch war (für fib(0)).

Möglicherweise ist es dann auf Haarspalterei hinausgelaufen. Es ist hier größtenteils ein Anfängerforum und wenn hier was steht, wird das auch für bare Münze genommen. Darum, wenn man Aussagen tätigt, sollten sie auch richtig sein. Mehr auch schon nicht.

Es ging immer um Variablen, darum stand auch "Variablen" in den Aussagen (und nicht Werte!). Darum kann ich dem nicht zustimmen, dass intern irgendwo eine weitere "Variable" auf magische Weise angelegt wird. Das hab ich gezeigt.

Genau genommen, wenn man sich den Bytecode ansieht beim ersten Beispiel - den ich auch kommentiert habe - sind im Stack zur selben Zeit maximal 3 Werte (wobei eine Zahl 2x vorkommt [Stack: fibN, fibSucc, fibSucc]) vorhanden. Darum braucht man immer nur 2 Werte (einer wird immer verworfen).

Nachdem das jetzt sicher Haarspalterei war: Stimme ich dem zu das du immer 3 Werte für den Algorithmus brauchst!

 

[Xyz1]

Mal vorweg. Ich habe meinen Code nicht gepostet, um zu zeigen wie man Variablen spart, sondern einfach weil der iterative Algorithmus HIER einfach falsch war (für fib(0)).

Deshalb auch meine Verbesserung, aber etwas selber nachdenken, hätte er auch selber können.

Wikipedia sagt übrigens aus, das 0 für n=0 und f_0 optional ist, genauso ob für negative Werte eine IAE geworfen werden sollte (was die rekursive Methode weiter verlangsamen würde).

fibN muss zwischengespeichert werden, anders geht es nicht (auch rechnerisch nicht), es kann nur kaschiert werden.

Mit "meiner" Methode kann "der Compiler" einfach 3 Register-Variablen daraus machen. Das ist ziemlich schnell, vom Speicherplatzverhalten akzeptabel, aber die Werte werden natürlich schnell sehr groß, weil die Werte quasi mit 2*n streng monoton wachsen.

Also von mir aus müssen wir uns nicht die Köpfe abhacken.^^

 

[Flown]

Also von mir aus müssen wir uns nicht die Köpfe abhacken.^^

Ich weiß nicht wieso, aber ich seh das ganz sachlich als fachliche Diskussion an. Aber zu einer Diskussion gehören auch Zahlen und Fakten.

Wikipedia sagt übrigens aus, das 0 für n=0 und f_0 optional ist, genauso ob für negative Werte eine IAE geworfen werden sollte (was die rekursive Methode weiter verlangsamen würde).

Optional stimmt, aber wenn f(0) vorhanden sein soll, dann soll auch "0" zurückgegeben werden und somit ist, wenn 1 zurückgegeben wird, das Ergebnis schlicht falsch.

Mit "meiner" Methode kann "der Compiler" einfach 3 Register-Variablen daraus machen. Das ist ziemlich schnell, vom Speicherplatzverhalten akzeptabel...

Vorweg: Man benötigt für eine Addition nur 2 Register auf Maschinenebene.
Der Bytecode wird noch in Maschinencode übersetzt und ich kann dir sagen, dass so ziemlich das Gleiche bei beiden Methoden rauskommen wird!

Bei anderer Ansicht bitte doch mal Fakten liefern eventuell Benchmarks/Profiles, damit man auch was dazulernen kann.

 

[kneitzel]

Flown: Deine Aussage bezüglich des Fehlers im Code verstehe ich nicht. fib(0) gibt doch 0 zurück und fib(1) und fib(2) beide 1. Einzige Diskussion könnte sein, ob fib von einer negativen Zahl 0 sein soll oder nicht.

Übersehe ich da etwas?

==> Ach ja - ich Blindfisch - geht ja um fibIter und nicht um fib! Sorry!

 

[Xyz1]

Optional stimmt, aber wenn f(0) vorhanden sein soll, dann soll auch "0" zurückgegeben werden und somit ist, wenn 1 zurückgegeben wird, das Ergebnis schlicht falsch.

Deshalb meine bereits erwähnte Verbesserung.

Vorweg: Man benötigt für eine Addition nur 2 Register auf Maschinenebene.
Der Bytecode wird noch in Maschinencode übersetzt und ich kann dir sagen, dass so ziemlich das Gleiche bei beiden Methoden rauskommen wird!

Bei anderer Ansicht bitte doch mal Fakten liefern eventuell Benchmarks/Profiles, damit man auch was dazulernen kann.

Ok, wir haben:

while (--n > 0) {

falsch,

while (--n >= 0) {

richtig,

for (int i = 0; i < n; i++) {

richtig, aber 4. Variable,

while (0 < n--) {

richtig, aber post-increment und echt kleiner,

daraus wird branch if equal, branch if not equal usw.

Ich behaupte jetzt, 1. post-increment ist langsamer als pre-increment, und 2. echt kleiner ist schneller als größer-gleich-als [*]. Somit heben sich beide wechselseitig auf. Damit wären wir beim Thema Mikrooptimierung, wonach wahrscheinlich nicht gefragt wurde.

[*] Weiß es jemand besser, möge er mich korrigieren.

Es müsste jetzt gemessen werden, die nicht rekursive Methode ist aber so schnell, dass ein messen mit long-Werten mir nicht sinnvoll erscheint.

 

[InfectedBytes]

pre/post inkrement unterscheiden sich nicht.

if(++i > 0) ...
//vs
if(i++ > 0) ...
//pre increment
iinc 1,1
load_1
...branch etc.
// post increment
load_1
iinc 1, 1
...branch etc.

iinc arbeitet direkt auf den lokalen Variablen und erhöht die Variable 1 eben um genau eins. load_1 lädt die entsprechende Variable auf den Stack. Wie man sieht unterscheidet sich nur die Reihenfolge und zwischen dem iinc und load wird keine Operation zwischen gelegt.

echt kleiner / kleiner-gleich ist schon eine etwas interessantere Frage, müsste aber ebenfalls exakt gleich sein.
Bei solchen spaßigen Architekturen wie MIPS gibt da tatsächlich unterschiede, da dort die Instruktionen asymmetrisch sind, aber bei x86 und co macht es keinen Unterschied. Allerdings bin ich mir hier nur zu 90% sicher^^

Aber wie du schon gesagt hast, wäre es so oder so eine super mikro optimierung^^