The Fibonacci sequence is one of the most discussed examples in computer science. One reason is that it is a simple but great example of recursion. It also helps us in understanding the trade-offs between time snd space complexity.

I today’s article, I will implement Fibonacci sequence in C++ in four different ways and also share the complexity numbers.

For those who need a refresher: the Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the two before it.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Formally: F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for all n > 1.

Implementation 1: Naive Recursion

The mathematical definition almost directly translates to code:

What is wrong with this algorithm? The time complexity is O(2^n) – that is exponential! The implementation might be OK for small values of N, but as N increases, the time complexity increases exponentially! Space complexity is just O(N).

Implementation 2: Recursion with Memoization

How can we do better? If we manage to “remember” previous call results, we don’t have to recompute already computed values. This will definitely save a lot of time! Here is an implementation that uses “memoization”.

I hope you get the logic. What is the complexity this time? Both Space and Time complexities are O(N)!

Implementation 3: Using Iteration

What if we decide to use “iteration” instead of “recursion”? Here is an implementation.

If the code looks a bit weird, it is only because I have used std::tie to advance both the state variables simultaneously in a single step without using any temporary variable.

As you can guess, the time complexity is O(N) and the space complexity is O(1)! The most efficient implementation of all!

Implementation 4: Using co_yield

The final implementation uses C++23 std::generator idea and is implemented as a coroutine. The “co_yield” keyword suspends the function mid-execution, hands a value back to the caller, and resumes exactly where it left off on the next request. The underlying implementation uses iteration.

Here also, the time complexity is O(N) and the space complexity is O(1).

I enjoyed revisiting fibonacci implementation after decades! Hope you find this article useful and interesting!

You can view the source code inside Compiler Explorer.