Fibonacci and Big-Oh reduction

I was asked to write some C# to implement a Fibonacci sequence, which falls into two parts: 1) generate a single number in the sequence, 2) generating the whole sequence.

Note that most examples of this sequence generator have a nasty bug in them. Most examples use the int data type, whilst this code uses the long data type, otherwise this function overflows around n=47.

The naive way to implement this is recursively:

  /// <summary>
  /// slow version of fib calc for testing - warning
  /// runs in O(1.618..n) 
  /// </summary>
  internal long Fibonacci(int n)
  {
   if (n < 2)
    return n;
   else
    return Fibonacci(n - 1) + Fibonacci(n - 2);
  }

And a more optimal approach is:

  /// <summary>
  /// returns the Fibonacci number for N
  /// </summary>
  public long Fibonacci(int n)
  {
   // returns N where n < 2, for higher values of N
   // avoids recursive solution by keeping track
   // of previous results

   long fn = 0;

   if (n < 0) // offset must be positive
    throw new NotSupportedException("Fibonacci sequence offset must be positive");
   else if (n < 2) // returns N where N < 2
    fn = n;
   else // use caching technique for higher values of N
   {
    long fnMinusTwo = 0;
    long fnMinusOne = 1;

    for (long ni = 2; ni <= n; ni++)
    {
     // effectively: fn = Fibonacci(n - 1) + Fibonacci(n - 2)
     fn = fnMinusOne + fnMinusTwo;

     fnMinusTwo = fnMinusOne;
     fnMinusOne = fn;
    }
   }

   return fn;
  }

The latter approach is much more efficient O(n) vs O(1.618..ⁿ). However its not as simple as the former. Another approach is to take the former solution and use a local cache:

  /// <summary>
  /// caching version of fib calc
  /// </summary>
  Dictionary<int, long> fibCache = new Dictionary<int, long>();
  internal long Fibonacci(int n)
  {
   long fn = 0;

   // use value from cache if already calculated
   if (fibCache.ContainsKey(n))
    return fibCache[n];

   // not cached, need to work it out
   if (n < 2)
    fn = n;
   else
    fn = Fibonacci(n - 1) + Fibonacci(n - 2);

   // add to cache
   fibCache.Add(n, fn);

   return fn;
  }

This gives us an O(n) runtime with a reasonably simple implementation. This is of course the classic trade-off of time vs. space - we have increased space used (the dictionary) to decrease time.

Finally we want to generate the whole sequence, which we can do in a lazy evaluation way using the yield keyword:

  /// <summary>
  /// returns the first N items in the Fibonacci sequence
  /// </summary>
  public static IEnumerable<long> FibonacciSequence(int n)
  {
   for (int fn = 0; fn < n; fn++)
    yield return Fibonacci(fn);
  }