6 ways to solve Fibonacci problem. Python

A Fibonacci sequence is a series of integers where the next number is found by adding up the two numbers before it

The formula can be visualised as follows

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

Fibonacci sequence is generally used as an introduction to dynamic programming and recursion for Computer Science students and is a common interview question.

In this post we show 6 ways to solve Fibonacci sequence problem in Python. From simple loops to using tabulation.

Quick reference

1. Solving Fibonacci using for loop
2. Solving Fibonacci using improved for loop
3. Solving Fibonacci using while loop
4. Solving Fibonacci using generator
5. Solving Fibonacci using recursion and memoization
6. Solving Fibonacci using tabulation
7. 3 fascinating facts about Fibonacci

Solving Fibonacci using for loop

    
def fib(n):
    fibonacci = [0, 1]
    if n>2:
        for i in range(2, n+1):
        next = fibonacci[i-1] + fibonacci[i-2]
        fibonacci.append(next)
    return fibonacci[n]
    

Solving Fibonacci using improved for loop

Improved space complexity, more concise code

    
def fib(n):
    fib1 = fib2 = 1
    for i in range(2, n):
        fib1, fib2 = fib2, fib1 + fib2
    return fib2

Solving Fibonacci using while loop

    
def fib(n):
    previous, before_previous = 0, 1
    i = 1
    while i < n:
        f_number = previous + before_previous
        previous = before_previous
        before_previous = f_number
        i += 1
    return f_number

Solving Fibonacci using generator

Yielding Fibonacci using the generator and while loop. Creating Fibonacci ‘on demand’ utilizing yield to separate apparent computation from the actual one. It allows generating each new Fibonacci number as needed, rather than computing a long sequence.

    
def gen_fib():
    fib_1 = 1
    fib_2 = 0
    while True:
        fib_next = fib_1 + fib_2
        yield fib_next
        fib_2 = fib_1
        fib_1 = fib_next

def fib(n: int) -> int:
    fib_n = gen_fib()
    if n == 0:
        return 0
    elif n == 1:
        return 1
    for i in range(1, n):
        if i == n-1:
            return(fib_n.__next__())
        else:
            fib_n.__next__()

Solving Fibonacci using recursion and memoization

    
def fib(n: int, memo={}) -> int:
    if n in memo.keys():
        return memo[n]
    if n <= 2:
        return 1
    else:
        memo[n] = fib(n-1)+fib(n-2)
        return memo[n]
    

Solving Fibonacci using tabulation

    
        def fib(n):
        table = [0 for i in range(n+1)]
        table[1] = 1
        for count in range(n):
        table[count+1] += table[count]
        if count < len(table)-2:
        table[count+2] += table[count]
        return table[n]
    

3 fascinating facts about Fibonacci

1. Fibonacci day is November 23 for the first numbers in sequence: 1123
2. The ratio of consecutive Fibonacci numbers converges and approaches The Golden Ratio:

           1 / 1 = 1
           2 / 1 = 2
           3 / 2 = 1.5
           5 / 3 = 1.667
           8 / 5 = 1.6
           13 / 8 = 1.625
           21 / 13 = 1.615
           34 / 21 = 1.619
           55 / 34 = 1.618
       

3. Every 3-rd Fibonacci number is a multiple of 2.

   Every 4-th Fibonacci number is a multiple of 3.

   Every 5-th Fibonacci number is a multiple of 5.

   Every 6-th Fibonacci number is a multiple of 8.