Fibonacci-Folge

Die Fibonacci-Folge beginnt mit 0 und 1, danach ist jede Zahl die Summe ihrer beiden Vorgänger: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 und so weiter.

Sie ist das Standardbeispiel für Rekursion, obwohl gerade sie zeigt, dass Rekursion nicht immer die richtige Wahl ist. Interessant ist sie außerdem, weil das Verhältnis zweier aufeinanderfolgender Zahlen sich dem goldenen Schnitt annähert.

Der naive rekursive Ansatz schreibt die Definition direkt hin: fib(n) = fib(n-1) + fib(n-2). Das ist elegant und in der Praxis eine Falle, denn dieselben Zwischenergebnisse werden immer wieder neu berechnet. Für fib(50) wären das über 25 Milliarden Aufrufe.

Die iterative Lösung merkt sich stattdessen nur die letzten beiden Zahlen und läuft einmal von unten nach oben durch:

1. Starte mit previous = 0 und current = 1.
2. Rücke n mal weiter: Das neue previous ist das alte current, das neue current ist die Summe beider.
3. Nach n Schritten steht die gesuchte Zahl in previous.

Damit braucht der Algorithmus genau n Additionen und zwei Variablen.

public static class Fibonacci
{
    // Berechnet die n-te Zahl der Folge 0, 1, 1, 2, 3, 5, 8, ...
    // Ab n = 93 passt das Ergebnis nicht mehr in ein long.
    public static long Calculate(int n)
    {
        ArgumentOutOfRangeException.ThrowIfNegative(n);

        var previous = 0L;
        var current = 1L;

        // Es werden nur die beiden letzten Zahlen gebraucht, zwei Variablen genügen.
        for (var i = 0; i < n; i++)
            (previous, current) = (current, previous + current);

        return previous;
    }

    // Liefert die ersten count Zahlen der Folge.
    public static IEnumerable<long> Sequence(int count)
    {
        var previous = 0L;
        var current = 1L;

        for (var i = 0; i < count; i++)
        {
            yield return previous;
            (previous, current) = (current, previous + current);
        }
    }
}

Console.WriteLine(string.Join(", ", Fibonacci.Sequence(12)));

Console.WriteLine(Fibonacci.Calculate(50));

// Der größte Wert, der noch in ein long passt.
Console.WriteLine(Fibonacci.Calculate(92));

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
12586269025
7540113804746346429

• Die Zahlen wachsen exponentiell. Ab n = 93 passt das Ergebnis nicht mehr in ein long, dann braucht man System.Numerics.BigInteger.
• Sequence ist ein Iterator: Die Werte entstehen erst beim Abholen, deshalb kann man damit auch endlos weiterlaufen, ohne vorher eine Liste zu bauen.
• Teilt man eine Fibonacci-Zahl durch ihren Vorgänger, nähert sich das Ergebnis dem goldenen Schnitt φ ≈ 1,618.