Fibonacci-Zahlen

Die berühmte Folge von Fibonacci-Zahlen ist folgendermaßen definiert:

$$a_{n+1} = a_n + a_{n-1} \qquad a_1=1, a_2 = 1, \qquad n > 1$$

Die ersten Glieder der Folge lassen sich damit leicht berechnen: $a_1=1$, $a_2=1$, $a_3=1+1=2$, $a_4=2+1=3$, $a_5=3+2=5$, $a_6=5+3=8$ usf. Wir formulieren dazu das folgende Java-Programm:

public class Fibonacci {

    static int fibonacci(int n) {
        if ((n==1) || (n==2)) return 1;
        else return fibonacci(n-1)+fibonacci(n-2);
    }

    public static void main (String [] args) {
        int maxzahl = Integer.parseInt(args[0]);
        for (int i = 1; i<=maxzahl; i++) {
            System.out.println(i + ": " + fibonacci(i));
        }
    }
}

Wir testen das Programm und erhalten:

alfred@duron:~/java/themen> java Fibonacci 6
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8

Die obige Folge wurde in Zusammenhang mit dem ``Kaninchenproblem'' zu Beginn des 13. Jh. entworfen: Ab dem 3. Lebensmonat wirft ein Kaninchenpaar in jedem Lebensmonat ein weiteres Kaninchenpaar. Alle Nachkommen verhalten sich ebenso...

Falls wir ein entsprechend großes Array für ganze Zahlen verwenden, lässt sich das Problem der Fibonaccizahlen auch iterativ formulieren:

public class FibonacciIt {
    public static void main (String [] args) {
        int maxzahl;
        maxzahl = Integer.parseInt(args[0]);
        int [] fib = new int [maxzahl+1];
        fib[1]=1;
        fib[2]=1;
        System.out.println("1: " + fib[1]);
        System.out.println("2: " + fib[2]);
        for (int i = 3; i <= maxzahl; i++) {
            fib[i] = fib[i-1] + fib[i-2];
            System.out.println(i + ": " + fib[i]);
        }
    }
}

In der Ausgabe erkennen wir keinen Unterschied zur rekursiven Lösung. Welche Lösung ist deiner Meinung nach ``eleganter''?

alfred@duron:~/java/themen> java FibonacciIt 6
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8