The Fibonacci series, runtime complexity and memoization

In this post we’ll look at an often recurring dev interview question: the Fibonacci series. The series is straightforward to build. The starting 0 and 1 are given and from then on each new number is calculated by adding the previous two numbers of the series. So the third element in the series will be 0 + 1 = 1, then 1 + 1 = 2 and so on. Here’s a short example:

The problem is most often presented as follows: write a function that returns the nth element of the Fibonacci series. The function will therefore accept an integer that denotes the position in the Fibonacci array. The index can be 0 or 1 based, this should be clarified with the interviewer. In this post will go for a 0-based solution, i.e. fib(2) must return the third element in the series, i.e. 1.

In this post we’ll go through 3 solutions:

• build the series in a loop until the required index has been reached
• recursion
• enhanced recursion

If you get this question in an interview then what they are really after is the two recursive solutions. We’ll find out why in just a bit. Here we’ll start with the easy solution that most people would think of, i.e. the iterative approach.

Let’s prepare a skeleton with the iterative implementation as it’s simple and straightforward:

using System;
using System.CodeDom;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms
{
    public class Fibonacci
    {        
        public int GetElementFromFibSeries(int index)
        {
            return BuildSeriesWithIteration(index + 1)[index]; //or .Last() LINQ           
        }

        private int GetFibElementWithRecursion(int index)
        {
            return 0;
        }

        private int GetFibElementWithMemoizedRecursion(int index)
        {
            return 0;
        }

        private List<int> BuildSeriesWithIteration(int howMany)
        {            
            if (howMany == 1) return new List<int>() { 0 };
            if (howMany == 2) return new List<int>() { 0, 1 };

            List<int> fib = new List<int>() { 0, 1 };            
            for (int i = 2; i < howMany; i++)
            {
                fib.Add(fib[i - 1] + fib[i - 2]);
            }
            return fib;
        }
    }
}

The BuildSeriesWithIteration function accepts an integer to indicate how many elements we want. As the leading 0 and 1 are given, we just return those lists without looking any further if the required size is 1 or 2. Otherwise we iterate from 2 until the required size and fill in the return list fib with the values calculated according to the formula presented above. Finally we return the list with the series.

We call this function from GetElementFromFibSeries. Recall that the index parameter is 0-based so we add 1 to it to get the correctly sized list of Fibonacci numbers. We only need the last value of that list which can be fetched using either the index parameter or the LINQ Last() operator.

Here comes a short test suite to see if everything works as intended:

using Microsoft.VisualStudio.TestTools.UnitTesting;
using Algorithms;
using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithms.Tests
{
    [TestClass()]
    public class FibonacciTests
    {
        [TestMethod()]
        public void BuildFibSeriesTests()
        {
            Fibonacci fib = new Fibonacci();
            Assert.AreEqual(0, fib.GetElementFromFibSeries(0));
            Assert.AreEqual(1, fib.GetElementFromFibSeries(1));
            Assert.AreEqual(3, fib.GetElementFromFibSeries(4));
            Assert.AreEqual(8, fib.GetElementFromFibSeries(6));
            Assert.AreEqual(34, fib.GetElementFromFibSeries(9));
            Assert.AreEqual(832040, fib.GetElementFromFibSeries(30));
        }
    }
}

Run the tests, they should pass.

Let’s now turn our attention to the recursive solution:

private int GetFibElementWithRecursion(int index)
{
    if (index < 2)
    {
        return index;
    }           

    return GetFibElementWithRecursion(index - 1) + GetFibElementWithRecursion(index - 2);
}

What is this?! That’s something that you should memorise for your job interview and not really think too much about what’s happening. This solution is very short and you’ll find a couple of variations of it by a simple Google search. We’ll give it a try anyway to see if we understand what’s going on.

So this is a recursive function which calls itself in twice in the same expression. Mentally it’s not easy to follow how the function is called, what is returned , when it stops and why it works. The key to keep in mind is that the ultimate return value is in the if block, that’s where the recursion is broken. Recursion is broken if the index is less than 2. If the index is less than 2 then we return the index itself. This means that at the end of the day we ultimately only return 0 or 1 from this function. The 0’s and 1’s are then added in…

return GetFibElementWithRecursion(index – 1) + GetFibElementWithRecursion(index – 2);

…therefore in reality we keep adding a series of 1’s. So how on Earth can this work properly?

Let’s add a Console.WriteLine statement to get some more information on what is going on here:

private int GetFibElementWithRecursion(int index)
{
    Console.WriteLine(string.Format("Calling recursive function with {0}", index));
    if (index < 2)
    {
        return index;
    }           

    return GetFibElementWithRecursion(index - 1) + GetFibElementWithRecursion(index - 2);
}

In the test suite comment out all Assert.AreEqual statements except for this one:

Assert.AreEqual(3, fib.GetElementFromFibSeries(4));

Run the test and you’ll get the following console output:

Calling recursive function with 4
Calling recursive function with 3
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 1
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0

As stated above the only real return value from this function is 1 and it is returned successively as the index parameter decreases with each iteration and reaches the value of 1. The 1’s are then added. Note how many times the recursive function was called with the argument of 1: 3 times, so we’ll end up with 1 + 1 + 1 = 3, which is the correct solution. Hmm, we’re onto something. Note that the function was called a total of 9 times for the incoming index 4.

Next only execute the following unit test:

Assert.AreEqual(8, fib.GetElementFromFibSeries(6));

Here’s the console output:

Calling recursive function with 6
Calling recursive function with 5
Calling recursive function with 4
Calling recursive function with 3
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 1
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 3
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 1
Calling recursive function with 4
Calling recursive function with 3
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0
Calling recursive function with 1
Calling recursive function with 2
Calling recursive function with 1
Calling recursive function with 0

Good grief, that’s 25 calls altogether and the function returned 1 exactly 8 times. So it looks like we found the essence of the function. Let’s just run the following unit test to make sure it’s not a coincidence:

Assert.AreEqual(34, fib.GetElementFromFibSeries(9));

I won’t paste the console output but the function was called 109 times in total, with index set to 1 exactly 34 times.

Now answer honestly: could you have come up with the recursive solution on your own without having seen it before in a stressful interview setting? For my part the answer is a resounding no. If you could do it then hats off to you, congratulations, you must be a genius. For everyone else just memorise it, it’s really not much. Also remember that we ultimately sum up a series of 1’s.

We’re not done yet. You see, this question leads to other areas in computing and algorithms that can be discussed, that’s why interviewers like it. We’ve already discussed recursion which is not exactly an overused language feature so some candidates might not even know that it exists. Another point to discuss is algorithm performance. Let’s summarise how many times the recursive function was called for each input:

I also executed the last unit test with index 30 but Visual Studio truncated the console output. We can conclude that with index 30 the function was probably called A LOT of times.

At this point the interviewer will ask you how efficient this algorithm is. Here (s)he wants to know if you’re familiar with (run)time complexity and the Big O notation. We can conclude based on the tabular data above that with each increase in the input, i.e. an increase in the index parameter, we see a significant increase in runtime as the recursive function is called over and over again multiple times. The increase in runtime increases exponentially with every increase of the input parameter. We call that exponential runtime and it’s denoted as follows using the Big O notation:

O(2^n)

It’s pronounced “o to the 2 to the n”. Normally we want to avoid algorithms that show this kind of behaviour. Exponential runtime is so inefficient that it should only be used as a last resort, if there’s really nothing else we can do to solve a problem. The iterative solution in BuildSeriesWithIteration had a linear runtime, which is denoted as follows:

O(n)

It’s pronounced “o to the n”. Why is it linear? It’s because of the for-loop. For each increase in the index parameter we must go one more step in the loop to build the Fibonacci series.

Note that if the index is 0 or 1 then we don’t even enter the loop but return immediately. For those two cases the function has a constant runtime denoted like this:

O(1)

…, i.e. “o to the one”. This means that no matter what index is, the algorithm will show the exact same efficiency, there’s no increase in processing power. However, the iterative function overall is O(n) because if different sections of a function display different runtimes then the higher order runtime wins. In this case O(n) > O(1), so overall we land at O(n).

Similarly the recursive function is O(1) if index is 0 or 1 but that’s quickly outranked by the exponential runtime. Therefore its overall runtime complexity is exponential.

We’re still not done. The next step is whether we can improve the performance of the recursive function. When you’re asked this question then you must be ready to respond with a resounding yes, using a technique called

memoization.

Yes, memoization and not memoRization. It’s an optimisation technique the is based upon the idea that if we feed the same input value(s) to a function then it should return the same result over and over again. It’s similar to caching in a way. If you take a look at the various console outputs above you’ll see that the recursive function calls itself with the same input argument several times. Our goal with memoization is to make the function remember the return value for a set of parameters. This way we can avoid a lot of round trips in the recursive function as the results can be pulled from this “cache” instead of going through all those iterative function calls.

The function returns an integer and accepts an integer. That sounds like our in-memory cache can be represented by a Map data structure, i.e. a Dictionary in .NET, where the key and the value are both integers. The key will be the index and the value will represent the calculated value.

Here’s the enhanced recursive function:

using System;
using System.CodeDom;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms
{
    public class Fibonacci
    {
        private readonly Dictionary<int, int> memo;

        public Fibonacci()
        {
            memo = new Dictionary<int, int>();
        }

        public int GetElementFromFibSeries(int index)
        {
            //return BuildSeriesWithIteration(index + 1)[index]; //or .Last() LINQ            
            //return GetFibElementWithRecursion(index);
            return GetFibElementWithMemoizedRecursion(index);
        }

        private int GetFibElementWithMemoizedRecursion(int index)
        {
            if (memo.ContainsKey(index))
            {
                Console.WriteLine(string.Format("Pulling solution of index {0} from the memo", index));
                return memo[index];
            }
            else
            {
                Console.WriteLine(string.Format("Index {0} not yet in memo", index));
                int solution;
                if (index < 2)
                {
                    solution = index;
                }
                else
                {
                    solution = GetFibElementWithMemoizedRecursion(index - 1) + GetFibElementWithMemoizedRecursion(index - 2);
                }
                memo[index] = solution;
                return solution;
            }
        }

        private int GetFibElementWithMemoizedRecursion(int index)
        {
            //truncated
        }

        private List<int> BuildSeriesWithIteration(int howMany)
        {            
            //truncated
        }    

    }
}

If memo contains the index key then we immediately return the value by that index. Otherwise we calculate the solution and put it into the map. I left a couple of console logging functions to check how many times we call the function.

Running the following unit test…

Assert.AreEqual(34, fib.GetElementFromFibSeries(9));

…produces the following log:

Index 9 not yet in memo
Index 8 not yet in memo
Index 7 not yet in memo
Index 6 not yet in memo
Index 5 not yet in memo
Index 4 not yet in memo
Index 3 not yet in memo
Index 2 not yet in memo
Index 1 not yet in memo
Index 0 not yet in memo
Pulling solution of index 1 from the memo
Pulling solution of index 2 from the memo
Pulling solution of index 3 from the memo
Pulling solution of index 4 from the memo
Pulling solution of index 5 from the memo
Pulling solution of index 6 from the memo
Pulling solution of index 7 from the memo

That’s 17 calls instead of 109 for index 9. That’s quite an acceptable improvement.

Many technical interview questions you encounter don’t reflect real life problems that have some business value or use-case in commercial software. It’s very unlikely that you ever have to implement the Fibonacci series using recursion in your project. However, these interview questions are a great way to test your basic training and eliminate candidates that lack knowledge in data structures, algorithms and basic language features. See how many areas we can cover with just this single question?

• collections
• iteration
• recursion
• runtime complexity
• memoization
• big O notation

If you get this question in your next job interview then you can easily spend an hour just talking about these concepts in computing based on it. You will score high and you can start getting ready for the next round 🙂