The following code shows a recursive method that calculates Fibonacci numbers:

// Calculate the Fibonacci number recursively.
private long RecursiveFibonacci(int number)
{
    checked
    {
        // On 0 or 1, return 0 or 1.
        if (number <= 1) return number;

        // Fibonacci(N) = Fibonacci(N - 1) + Fibonacci(N - 2).
        return
            RecursiveFibonacci(number - 1) +
            RecursiveFibonacci(number - 2);
    }
}

This method simply follows the recursive definition of Fibonacci numbers.

Fibonacci numbers grow very quickly (although not as quickly as the factorial function), so the program uses a checked block to protect itself from integer overflow errors.

Unfortunately, this method has a more pressing problem—it recalculates certain values a huge number of times. For example, suppose you want to calculate F_N. To do that, the method calls itself to calculate F_N-1 and F_N-2. Then, to calculate F_N-1, the method calls itself to calculate F_N-2 and F_N-3. Here, the method is calculating F_N-2 twice.

If you follow the recursive calls further, you'll find that the method calls itself to recalculate the same values an enormous number of times. The following diagram shows the calls needed to calculate F5:

You can see in the preceding diagram that the values F₁ and F₀ are calculated many times. Those values are easy to calculate, but if the tree were bigger, the method would also calculate more complicated values many times. The following table shows the total number of times the method is called while calculating various Fibonacci numbers:

You can see from the preceding table that the number of method calls grows very quickly. The method calls itself so many times that it cannot calculate values larger than around F₄₅ in a reasonable amount of time.

In cases such as this, you need to remove the need for all of the duplicate calculations. One way to do that is to change the way you think about the recursive definition of Fibonacci numbers. Recall the following definition:

 for  N>1

The previous method used a top-down approach, where it started with a large value (say F₁₀) and then recursively called itself to calculate the smaller values needed to build that value (F₉ and F₈).

Alternatively, you can take a bottom-up approach, where you build smaller values and then use them to create larger ones. The following method uses the bottom-up approach:

// Calculate the Fibonacci number non-recursively.
private long NonRecursiveFibonacci(int number)
{
    checked
    {
        // On 0 or 1, return 0 or 1.
        if (number <= 1) return number;

        // Start at i = 2.
        long fiboIMinus2 = 0;                   // Fibonacci(0)
        long fiboIMinus1 = 1;                   // Fibonacci(1)
        long fiboI = fiboIMinus1 + fiboIMinus2; // Fibonacci(2)
        for (int i = 2; i < number; i++)
        {
            // Update the values.
            fiboIMinus2 = fiboIMinus1;
            fiboIMinus1 = fiboI;
            fiboI = fiboIMinus1 + fiboIMinus2;
        }
        return fiboI;
    }
}

This method uses variables to hold the values F_i, F_i-1, and F_i-2 as it performs its calculations. It enters a loop where it uses F_i-1 and F_i-2 to calculate F_i until it has calculated the value it needs.

This version calculates each Fibonacci value once. For example, to calculate F₄₀, it calculates F₀, F₁, and F₂, and so on for a total of 40 calculations instead of the 331 million required by the recursive method.

This non-recursive version is extremely efficient, but it's also rather confusing because it requires you to keep track of which variables hold which values.

A table of values can sometimes make this sort of recursion removal easier to understand. The following method stores values in an array and then fills the array until it has calculated the value that it needs:

// Use a table to calculate the Fibonacci number non-recursively.
private long TableFibonacci(int number)
{
    checked
    {
        // Make a table to hold Fibonacci values.
        long[] values = new long[number + 1];

        // Initialize Fibonacci(0) and Fibonacci(1).
        values[0] = 0;
        values[1] = 1;

        // Fill the table.
        for (int i = 2; i <= number; i++)
            values[i] = values[i - 1] + values[i - 2];

        // Return values[number].
        return values[number];
    }
}

This version is also fast and effective. Its one drawback is that it recreates the table every time it calculates a Fibonacci value. It might be nice to keep any previously calculated values for later use. The following method uses a cache to hold values in case they are needed later:

// Use a cache table to calculate the Fibonacci number non-recursively.
private long[] FibonacciCache = null;
private long CachedFibonacci(int number)
{
    // Initialize the cache if necessary.
    if (FibonacciCache == null)
    {
        // Initialize the table to hold all -1 entries.
        // Fibonacci(92) is the largest value that doesn't overflow.
        const int MaxNumber = 92;
        FibonacciCache =
            Enumerable.Repeat(-1L, MaxNumber + 1).ToArray();

        // Initialize Fibonacci(0) and Fibonacci(1).
        FibonacciCache[0] = 0;
        FibonacciCache[1] = 1;
    }

    // Use the cache to calculate the Fibonacci number.
    checked
    {
        // We don't have the value. Calculate and save it.
        if (FibonacciCache[number] < 0) FibonacciCache[number] =
            CachedFibonacci(number - 1) +
            CachedFibonacci(number - 2);

        // Return the cached value.
        return FibonacciCache[number];
    }
}

This code defines the cache array outside the method. When the method starts, it checks the cache to see if it has been initialized. If the cache is null, the method creates a new array with each entry set to -1. It then initializes the first two values to F₀ = 0 and F₁ = 1. (The method gives the array 93 positions with indices 0 through 92 because F₉₂ is the largest Fibonacci number that fits in a long integer.)

The method then checks the cache to see if it has already calculated the value that it needs. If the value is not yet in the cache, the method calls itself recursively to store that value in the array. It can then return the desired value.

This method follows the same general approach as the initial recursive approach. The big difference is that it stores any value that it calculates so that it doesn't need to calculate the same values again and again. For example, if you look back at the earlier diagram, you'll see that the tree calculates F₄ twice. The new method would only calculate that value once and save it, so it would chop off the entire F₄ subtree from the calculation. When calculating larger values, the savings are huge.

Even better, after a while the cache table will contain all of the Fibonacci numbers up to F₉₂, so the method will never need to perform new calculations. You could even prefill the table when the program starts so that the method can look up values later.

There's one more point about this example worth mentioning. Fibonacci numbers don't grow as quickly as factorials, but they do grow quickly, so large Fibonacci numbers will overflow 64-bit long integers. For that reason, the methods protect themselves with checked blocks.

To summarize, there are several lessons to be learned from this example. First, if a recursive solution works and is easy to understand, then use it. If a recursive approach recalculates the same values many times, try a bottom-up approach. If a bottom-up approach is confusing, consider saving intermediate values in a table. Finally, if you're using a table, ask yourself whether it's worth converting the table into a cache so that you can reuse saved values later.

Download the FibonacciNumbers example solution to see additional details.