For some background on Fibonacci numbers and φ, see Examine the relationship between the Fibonacci sequence and phi in C#.

This example shows several ways to calculate Fibonacci numbers. While this is mostly for curiosity's sake, there are a couple of lessons here about recursion and look-up tables.

Recall the recursive definition of the Fibonacci numbers:

    Fibonacci(0) = 0
    Fibonacci(1) = 1
    Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2)

This recursive definition leads naturally to this recursive algorithm for calculating Fibonacci numbers.

// Recursive.
private double Fibonacci1(int n)
{
    if (n <= 1) return n;
    return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}

This method is simple. Unfortunately it's also very slow. For example, to calculate Fibonacci(40) the program must calculate Fibonacci(39) and Fibonacci(38). But to calculate Fibonacci(39) the program must calculate Fibonacci(38) and Fibonacci(37). Here Fibonacci(38) is being calculated twice. As the recursion continues, the same values must be calculated again and again a huge number of times making the program take a very long time.

The following method solves the problem of recalculating values by storing the intermediate values it creates in a look-up table for later use.

// With look-up values.
private double Fibonacci2(int n)
{
    if (n <= 1) return n;

    // Create the look-up table.
    double[] fibo = new double[n + 1];
    return Fibonacci2(fibo, n);
}
private double Fibonacci2(double[] fibo, int n)
{
    if (n <= 1) return n;

    // If we have already calculated this value, return it.
    if (fibo[n] > 0) return fibo[n];

    // Calculate the result.
    double result =
        Fibonacci2(fibo, n - 1) +
        Fibonacci2(fibo, n - 2);

    // Save the value in the table.
    fibo[n] = result;

    // Return the result.
    return result;
}

The first version of the method makes a look-up table big enough to hold the Fibonacci numbers 0 through n. It then calls the second overloaded version to do all the work, passing it the look-up table and n.

The second version of Fibonacci2 looks in the look-up table to see if we have already calculated the n-th Fibonacci number and returns it if we have. This prevents the method from calculating the same values more than once and saves a huge amount of time.

If we have not yet calculated the n-th Fibonacci number, the method calls itself recursively as before, saves the value it calculates in the look-up table, and returns the result it calculated.

This technique of caching values that you will need later can be extremely powerful. It can let you avoid a lot of work even if you don't really know when you'll need the values later. (I worked on a project once where some performance analysis showed that a lot of time was spent calculating the same values repeatedly. I added a look-up table and improved performance greatly.)

This method is a great improvement on the previous version but there's still room for improvement. Both of the previous methods generate Fibonacci numbers in a top-down way, but the recursive definition of the Fibonacci numbers is really bottom-up. The definition starts with Fibonacci(0) and Fibonacci(1) and works up from there.

The following method uses a bottom-up approach to build Fibonacci numbers without recursion.

// Iterate holding the two previous values.
private double Fibonacci3(int n)
{
    if (n <= 1) return n;

    double minus2 = 0;
    double minus1 = 1;
    double fibo = minus1 + minus2;
    for (int i = 3; i <= n; i++)
    {
        minus2 = minus1;
        minus1 = fibo;
        fibo = minus1 + minus2;
    }
    return fibo;
}

The method creates variables minus2, minus1, and fibo. When fibo holds Fibonacci(n), minus2 holds Fibonacci(n - 2) and minus1 holds Fibonacci(n - 1).

Initially minus2 = Fibonacci(0), minus1 = Fibonacci(1), and fibo = Fibonacci(2).

The method then enters a for loop. Each trip through the loop, the code moves minus2 up to the current value of minus1, minus1 up to the current value of fibo, and calculates the next value for fibo. When the loop finishes, fibo holds Fibonacci(n).

This method doesn't use recursion and doesn't need a look-up table so it's even faster than the previous method (and uses less memory), but even it can be improved. Abraham de Moivre discovered that:

    Fibonacci(n) = (φ1n - φ2n) / Sqrt(5)

Where φ₁ and φ₂ are the two roots to the equation for the golden ratio. (See the earlier post.)

    φ1 = (1 + Math.Sqrt(5)) / 2
    φ2 = (1 - Math.Sqrt(5)) / 2

The following method uses de Moivre's formula to calculate Fibonacci numbers directly.

// Use Abraham de Moivre's formula.
private double Fibonacci4(int n)
{
    double phi1 = (1 + Math.Sqrt(5)) / 2.0;
    double phi2 = (1 - Math.Sqrt(5)) / 2.0;
    return (Math.Pow(phi1, n) - Math.Pow(phi2, n)) / Math.Sqrt(5);
}

Even this can be simplified (but I promise this is the last one). Because the absolute value of φ₂ is less than 1 (it's roughly -0.62), φ₂ⁿ is small for all n so you can drop that term and round the result off to the nearest integer.

// Ignore phi2.
private double Fibonacci5(int n)
{
    double phi1 = (1 + Math.Sqrt(5)) / 2.0;
    return Math.Truncate(Math.Pow(phi1, n) / Math.Sqrt(5));
}

The lessons to learn are:

• Whenever you have recursion, be aware of whether you are calculating the same value many times.
• Whether you have recursion or not, if the program is recalculating the same values many times, you may be able to speed things up by creating a look-up table so you only need to calculate each value once.
• If a recursive relationship is defined in a bottom-up way, you may be able to create an iterative solution that also works in a bottom-up way without recursion.
• The formula discovered by de Moivre is specific to Fibonacci numbers so you probably won't be able to use it unless you are calculating Fibonacci numbers, but the final method used by this example actually holds a lesson that is more general. If you're calculating a numeric result and part of the result quickly becomes very small, you may be able to ignore it. In particular, if you're calculating an integer result, you may be able to ignore parts of the equation that contribute only a small amount to the result.