Fibonacci Sequence

The Fibonacci sequence starts with 0 and 1, and from there every number is the sum of its two predecessors: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 and so on.

It is the standard example for recursion, even though it is exactly the case that shows recursion is not always the right choice. It is also fascinating because the ratio of two consecutive numbers approaches the golden ratio.

The naive recursive approach writes down the definition directly: fib(n) = fib(n-1) + fib(n-2). That is elegant and a trap in practice, because the same intermediate results are calculated again and again. For fib(50) that would be more than 25 billion calls.

The iterative solution instead remembers only the last two numbers and walks upwards once:

1. Start with previous = 0 and current = 1.
2. Step forward n times: the new previous is the old current, the new current is the sum of both.
3. After n steps the wanted number is in previous.

That way the algorithm needs exactly n additions and two variables.

public static class Fibonacci
{
    // Calculates the n-th number of the sequence 0, 1, 1, 2, 3, 5, 8, ...
    // From n = 93 on the result no longer fits into a long.
    public static long Calculate(int n)
    {
        ArgumentOutOfRangeException.ThrowIfNegative(n);

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

        // Only the two most recent numbers are needed, so two variables are enough.
        for (var i = 0; i < n; i++)
            (previous, current) = (current, previous + current);

        return previous;
    }

    // Returns the first count numbers of the sequence.
    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));

// The largest value that still fits into a long.
Console.WriteLine(Fibonacci.Calculate(92));

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

• The numbers grow exponentially. From n = 93 on the result no longer fits into a long, and you need System.Numerics.BigInteger.
• Sequence is an iterator: the values are created while they are pulled, so you can keep walking endlessly without building a list first.
• Divide a Fibonacci number by its predecessor and the result approaches the golden ratio φ ≈ 1.618.