How to implement Fibonacci Sequence with Python

Fibonacci sequence is one of the most popular interview questions. There are several ways to implement it with Python. Let's see how to do that.

Fibonacci Sequence

The Fibonacci Sequence is the series of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The next number is found by adding up the two numbers before it.

• The 2 is found by adding the two numbers before it (1+1)
• The 3 is found by adding the two numbers before it (1+2),
• And the 5 is (2+3),
• and so on!

The rule of Fibonacci Sequence is

x(n) = x(n-1) + x(n-2)

where:

x(n) is term number "n"

x(n-1) is the previous term (n-1)

x(n-2) is the term before that (n-2)

source : https://www.mathsisfun.com/numbers/fibonacci-sequence.html

Method 1 : With for loop

# using for loop 

def fibonacci_loop(num):
    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    elif num > 2:
        a = 1 # variable for (n - 1)
        b = 1 # variable for (n - 2)
        for _ in range(3, num + 1):
            c = a + b
            a, b = b, c

        return c

%time fibonacci_loop(40)
    CPU times: user 6 µs, sys: 0 ns, total: 6 µs
    Wall time: 8.11 µs
    102334155

With recursion

We can solve the problem with for-loop, but it is not so intuitive.

From the rule of fibonacci sequence x(n) = x(n-1) + x(n-2) ,

we can make a function that call itself,
it is called recursive function.

# Recursive Method 1 : traditional recursive function

def fibonacci_recursion(num):
    '''Return a fibonacci sequence value of num'''
    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1

    return fibonacci_recursion(num - 2) + fibonacci_recursion(num - 1)

%time fibonacci_recursion(40)
    CPU times: user 26.5 s, sys: 64 ms, total: 26.6 s
    Wall time: 26.6 s
    102334155

Quiet slow??

It takes more and more time while the number is increased.

Because the function itself is needed to calculate same value over and over.

We can reduce total number of calling the function with saving the result to cache.

# Recursive Method 2 : With using explicit cache
cache = {}

def fibonacci_cache(num):
    '''Return a fibonacci sequence value of num'''

    if num in cache:
        return cache[num]

    if num == 0:
        result = 0
    elif num == 1 or num == 2:
        result = 1
    else:
        result = fibonacci_cache(num - 2) + fibonacci_cache(num - 1)

    cache[num] = result
    return result

%time fibonacci_cache(40)
    CPU times: user 2 µs, sys: 0 ns, total: 2 µs
    Wall time: 5.01 µs
    102334155

same result but super faster than normal recursive function

Using LRU cache

Python provides a functools library helps the recursive function calls,

let's use Least Recently Used cache (lru_cache) from functools

# import library
from functools import lru_cache

# Recursive Method 3 : with implicit cache provided by functools

# set cache with 1000 (need to set a big values, small cache is NOT useful)
@lru_cache(maxsize = 1000)

def fibonacci(num):
    '''Return a fibonacci sequence value of num'''

    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1

    return fibonacci(num - 2) + fibonacci(num - 1)

%time fibonacci(40)
    CPU times: user 3 µs, sys: 0 ns, total: 3 µs
    Wall time: 5.25 µs
    102334155

Little differ time values, but it could be ignored. (just some micro seconds)

Conclusion

We need to set lru_cache when using recursive function for performance

Source : https://github.com/Teosoft7/fibonacci_python.git