Printing Fibonacci sequence up to n.

  • Below I have re-produced a number of common approaches to calculating Fib(n);
  • Then to print the sequence of Fib(n) we can iterate over all numbers between 0 and numOfFibElements.

Without caching

Runtime of Fibonacci(int n): \(O(n^2)\)

private static void Main()
{
    var numOfFibElements = 15;
    var results = new List<int>();
    for (int i = 0; i <= numOfFibElements; i++)
        results.Add(Fibonacci(i));

    Console.WriteLine(string.Join(", ", results));
}

public static int Fibonacci(int n)
{
    if (n <= 1)
        return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}
  • So if we pass in 5:
    • We get a binary call tree result where each child node is either n-1 or n-2 until we reach 0 or 1.
    • We sum these values to get our total result, in this case we get 1, 0, 1, 1, 0, 1, 0, 1 on the leaves, ie 5.
    • We can see when doing this that we get repeated nodes, 3 twice and 2 three times.
    • Storing a cache for these repeated requests will reduce our space requirements (fewer calls on the stack vs the cache), and reduces runtime.

n = 15 produces:

  • 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610.

Adding a cache:

Runtime \(O(n)\), Space \(O(n)\)

public static int Fibonacci(int n, int[] cache)
{
    if (n <= 1)
        return n;

    if (cache[n] == 0)
        cache[n] = Fibonacci(n - 1, cache) + Fibonacci(n - 2, cache);

    return cache[n];
}

Iterative Fibonacci

Runtime \(O(n)\), Space / Memory \(O(1)\)

public static long Fibonacci(long n)
{
    long a = 0;
    long b = 1;
    for (long i = 0; i < n; i++)
    {
        long temp = a;
        a = b;
        b = temp + b;
    }

    return a;
}

Resources: