Fibonacci solution in Python

I have always thought of the Fibonacci sequence as a suitable challenge when learning a new programming language. According to Wikipedia “the Fibonacci numbers, commonly denoted F_n form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1“. I posted my JavaScript solutions to solve the Fibonacci value for n where F_n = F_n-1 + F_n-2 here. In this post, I have taken a pass at a few possible Python solutions each with seed values F₀ = 0 and F₁ = 1.

The first obvious solution would be a iterative solution where the code follows the mathematical formula like:

def f(n: int) -> int:
     """Return the Fibonacci number for n by iterating over a list."""
     result = [0, 1]
     idx = 2
     if n == 0: return 0
     elif n == 1: return 1
     else:
         while idx < n:
             result.append(result[idx - 1] + result[idx - 2])
             idx += 1
     return int(result[n - 1]) + int(result[n - 2])

This solution first generates the sequence up to n in a list and then calculates the value at index n. It works but not very efficient with large indices. We can, however, improve the efficiency of the code solution by eliminating the need to generate the sequence in order to calculate the value at index n. For example:

def f1(n: int) -> int:
     """Return the Fibonacci number for n by iteration."""
     if n == 0: return 0
     elif n== 1: return 1
     elif n== 2: return 1
     else:
         f1, f2 = 1, 1
         for i in range(2, n):
             fn = f1 + f2
             f1, f2 = f2, fn
     return fn

Here, we calculate the value at index n using a for loop without the need for a list. We are down to one calculation per loop compared to two calculations per loop in the first iterative solution. This is a better solution but surely we can improve efficiency. Let’s take a look at a recursive solution:

def f2(n):
     """Return the Fibonacci number for n by recursion."""
     if n == 0:return 0
     elif n == 1:return 1
     else:
         fn = f2(n-1) + f2(n-2)
         return fn

A recursive function is one where the function calls itself one or more times in its body. It is important to ensure that there is a way for a recursive function to terminate. Again, we see degradation with larger indices.

For the purposes of this post, I started to investigate the concept of memoization as implemented in Python. One possible way to memoize the recursive function could be:

def f3(n, _cache={}):
     """Return the Fibonacci number for n using a memoized recursive function"""
     if n in _cache: return _cache[n]
     elif n > 1:
         return _cache.setdefault(n, f3(n-1) + f3(n-2))
     return n

Memoization suits the Fibonacci problem adequately since you can store the results of calculations that you have done before and return a stored result rather than repeating the calculation. Performance is noticeably better at higher indices when compared to the previous solutions.

Leave a Reply Cancel reply