Fibonacci Sequence: Recursive and Iterative solutions (Dynamic Programming)

While studying Algorithms, you'll definitely encounter the problem of calculating the Fibonacci sequence. Here's a small post showing you 3 methods (Recursive, Top-down and Bottom-up) along with their time and space complexities do to it.

Here we go.

Recursive

def FibonacciRec(n):

    if (n == 0 or n == 1):
        return n

    return FibonacciRec(n - 1) + FibonacciRec(n - 2)

Time complexity: O(2^n)
Space complexity: O(n)

This above recursive solution is a naive approach. Following two are the better approaches to do the same thing. I've implemented them in a single class FibonacciCalc.

Top-down (Memorization) and Bottom-up (Dynamic Programming)

class FibonacciCalc:

    def __init__(self):
        self.memory = {}


    def FibonacciTopDown(self, n):
        if (n == 0 or n == 1):
            return 1

        if (n in self.memory):
            return self.memory[n]
        
        ret_value = self.FibonacciTopDown(n - 1) + self.FibonacciTopDown(n - 2)
        
        self.memory[n] = ret_value

        return self.memory[n]


    def FibonacciBottomUp(self, n):
        if (n == 0 or n == 1):
            return 1

        prev = current = 1

        for i in range(2, n + 1):
            tmp = current
            current += prev
            prev = tmp

        return current

Time and space complexity for the Top-down approach: O(n)

Time and space complexity for the Bottom-up approach: O(n) and O(1) respectively.

There you go.
Have fun!