The Fibonacci sequence (or series) is a classic example of a problem that can be solved by using recursion. As such, it’s often used to teach the concept of recursion in introductory programming courses. In this post, I’m going to explain how to write a simple recursive Fibonacci sequence calculator in C++ and how to optimize it so that it is capable of computing large Fibonacci numbers more efficiently.

Some Background: What is Recursion?

If you’re already familiar with the concept of recursion, you’re welcome to skip to the next section, where I’ll jump right into the code. Otherwise, you may want to review this section before continuing.

An Informal Definition

Put most simply, a recursive problem is one that is defined in terms of itself. In computer science, recursive procedures (functions) are used to break these kinds of problems down into simpler, easier-to-solve versions of themselves. Recursive functions, like the problems they solve, are also defined in terms of themselves.

Recursion in Code

In practice, this means a recursively defined function must call itself when it runs. To prevent an infinite loop, a correctly written recursive function will stop calling itself once it reaches a base case, which is a problem it can solve without having to call itself again. This is the idea behind recursion: A complex problem is eventually reduced to an easy-to-solve base case with a known solution. Recursive functions achieve this goal by re-using the same logic with different parameters every time the function is recursively called.

Recursion and the Fibonacci Sequence

With this in mind, it’s easy to see why the Fibonacci sequence is a good example of recursion. In the Fibonacci sequence, each number is recursively defined as the sum of the two previous numbers. For example, to find the fifth Fibonacci number, you first have to find the third and fourth numbers. However, you can’t find the fourth number without finding the second and third numbers, and so on. In fact, the whole sequence is constructed from the first two numbers, 0 and 1, which are the base cases. Some recursive problems only have one base case, but the Fibonacci sequence has two.

The Simple Function (And Why It’s So Slow)

All of this can be expressed more clearly with code:

 1 int fibonacci(int n) {
 2     if (n == 0) {
 3         return 0;
 4     } else if (n == 1) {
 5         return 1;
 6     } else {
 7         return fibonacci(n-1) + fibonacci(n-2);
 8     }
 9 }

This basic fibonacci function takes a single integer n as a parameter. This integer is the index value of the desired Fibonacci number. The first two if statements (lines 2 and 4) are simple: If the 0th Fibonacci number is requested, return 0. If the 1st Fibonacci number is requested, return 1.

However, if anything beyond the 1st Fibonacci number is requested, the function jumps to the statement in the last else block (line 7):

return fibonacci(n-1) + fibonacci(n-2);

In this case, the function will first compute the previous two values of the sequence, and then add them together and return the answer. This is because the value of fibonacci(2) depends on the values of fibonacci(1) and fibonacci(0), and so on.

This quickly becomes complex. Calling fibonacci(5) results in calls to fibonacci(4) and fibonacci(3). However, calling fibonacci(4) results in a second call to fibonacci(3), since we need to know the value of the 3rd number in the sequence before we can find the value of the 4th. Likewise, both calls to fibonacci(3) will result in duplicate calls to fibonacci(2) (and eventually fibonacci(1) and fibonacci(0)).

Re-computing values we’ve already calculated is a big performance drain, and it only gets worse as we go farther into the sequence. Wouldn’t it be great if we could store the value of fibonacci(3) somewhere so we didn’t have to re-compute it later?

The Optimized Function

 1 unsigned long fibonacci(unsigned long n) {
 2         static std::vector<unsigned long> fibovector = {0, 1};
 3         unsigned long temp;
 4         if (n < fibovector.size()) {
 5                 return fibovector[n];
 6         } else {
 7                 temp = fibonacci(n-1) + fibonacci(n-2);
 8                 fibovector.push_back(temp);
 9                 return temp;
10         }
11 }

In this optimized version of the fibonacci function, I’ve added a vector (called fibovector) that caches the computed values. I’ve also changed the base case: The function no longer checks to see if the requested value is 0 or 1 but instead checks to see if the value is cached in the vector (line 4). If the requested value is already stored in the vector, the function uses the cached value and skips having to re-compute it. If it’s not already cached, the function recursively computes it (line 7) and then adds it to the vector for later use.

The Vector

There’s a few important points worth noting regarding the vector. The vector is declared with the static keyword so that its contents can persist between function calls. To get the program started, the vector is “preloaded” with the first two values in the Fibonacci sequence, 0 and 1. These are the initial base cases for the function.

Because the vector gets populated in order, there’s an easy way to check if the desired value is already cached or not. Since the index values of the numbers in the vector correspond to the actual index values of the numbers in the Fibonacci sequence, you can simply compare the desired index value with the size of the vector. If the requested index value is less than the size of the vector (line 4), the function has already cached that value. It’s important to keep in mind that this works because the largest index value in a vector is always one less than the total number of elements it contains (the size) since index values start at 0.

Why unsigned long?

Fibonacci numbers get very large very quickly, and due to the nature of how computers store numerical data it’s easy to overflow your chosen data type before getting very far. There’s a section about integer overflow at the end of this article about email servers, but the bottom line is that the 46th number in the Fibonacci sequence is the largest Fibonacci number that can be stored in a 32-bit integer. With unsigned long as the data type, we’re able to store up to the 93rd Fibonacci number before overflowing that data type as well. To keep the function simple, I’ve opted to use native C++ data types instead of writing or importing a custom “big integer” class that would allow for the storage of even larger Fibonacci numbers.

Checking Your Work

To test if your program is working correctly, you can compare its output to the list of the first 2000 Fibonacci numbers published by the On-Line Encyclopedia of Integer Sequences (OEIS).

Then, try timing each program and comparing how long they both take to reach the 46th Fibonacci number. The results might surprise you.