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..n). 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);
}
