fib.py

"""
Method 1: iterative:
"""
def fib1(self, N):
    if N <= 1: return N
    a, b = 0, 1
    for _ in range(2, N + 1):
        a, b = b, a + b
    return b
    
"""
Method 2: recursive without memorization:
"""
def fib2(self, N):
    if N <= 1: return N
    return self.fib(N - 1) + self.fib(N - 2)

"""
Method 3: recursive with memorization
"""
def fib3(self, N):
    memo = {0:0, 1:1}
    def helper(n):
        if n not in memo:
            memo[n] = helper(n - 1) + helper(n - 2)
        return memo[n]
    return helper(N)