There's more than one way to do things. There's always different points of views and styles of pitching. ~Tim Hudson

In this article, we will use three different techniques in Python to code a basic Fibonacci program which will give the sum of the sequence as a result. The Fibonacci sequence is 0,1,1,2,3,5,8...

As you may have noticed, we add the first and second numbers, 0 and 1, to get the third number in the sequence (1) -> 0+1=1. Then we add the second and third numbers, 1+1=2, to get the 4th number in the sequence...and so on.

You can implement this code in Jupyter, Colab or any IDE or text editor you feel comfortable with.

How to Code the Fibonacci Sequence Using a For Loop in Python

Here, I have written a basic Fibonacci program using a for loop in Python. The logic behind this is simple and we already discussed it above.

The time complexity is O(N) and space complexity is O(1) or constant. But, it is actually more complicated than this complexity implies.

"If your number is less than N < 94, and you use a 64 bit integer, then the algorithm acts as a linear complexity. However, for N > 94 it starts to behave like a quadratic complexity algorithm." ~ Michael Veksler
serverCode_foR_1
Printing a Fibonacci result using a For Loop

I am going to run this with Python's %timeit module. This avoids a number of common traps for measuring execution times. You can see more uses here.

serverCode_foR_R_1
It took 675 nanoSec per loop for 10

How to Code the Fibonacci Sequence with Recursion in Python

Here, we will implement the sequence using recursion. Recursive functions tend to call themselves on repeat until they reach the base case. So, recursion creates a tree structure.

If we take a Fibonacci series of 5, this is the tree which will be created by recursion.

serverCode_foR_R2_1

The Space Complexity is O(N) and the Time complexity is O(2^N) because the root node has 2 children and 4 grandchildren. And, as you can see, every node has 2 children.

Now the depth is N, which means that we have to do this N times. Also, you may have noticed that the right sub-tree is smaller than the left sub-tree, so the true runtime is roughly O(1.6^N).

The base case: Fibonacci(2) = Fib(1) + Fib(0)  = 1 + 0 = 1

serverCode_Recur_op_2
Printing Fibonacci result using Recursion

The Recursive Fibonacci example is definitely faster than the for loop.

serverCode_Recur_R_2

How to Code the Fibonacci Sequence Using Memoisation in Python

Memoisation is a technique which can significantly improve a recursive function's performance by reducing the computational liability.

It stores the results of expensive function calls in an array or dictionary and returns the cached results when the same input is called.

You can see the above tree for reference, and how certain inputs keep getting recomputed on each call to them.

serverCode_Memo_op_3
Printing Fibonacci result using Memoisation

The time complexity is O(nlogn).

serverCode_Memo_R_3

Which is better, recursion, for-loops, or memoisation?

Now, these techniques aren't supposed to be better than one another. You simply need to know when you need to use which one. Which of course depends on your requirements.

Iteration will be faster than recursion because recursion has to deal with the recursive call stack frame. But, if recursion is written in a language which optimises the tail call, then it eliminates the overhead and is almost on par with for loops.

Lastly, memoisation is better whenever the state space is sparse, that is not all smaller sub-problems need to be solved, but only a few of them.

Thanks for reading! If you liked this article, you can read my other articles here. You can show your appreciation for this article by sharing it. Also you can connect with me on LinkedIn.