fibonacci.py

def fibonacci(n):
    """ recursive Fibonacci, naive """
    if n <= 2:
        return 1
    else:
        return fibonacci(n-2) + fibonacci(n-1)

count = 0

def count_fibonacci(n):
    """ recursive Fibonacci plus counting no. of function invocations """
    global count
    count += 1
    if n <= 2:
        return 1
    else:
        return count_fibonacci(n-2) + count_fibonacci(n-1)

# initial fib dictionary with first two elements
fib_dict = {1:1, 2:1}

def fibonacci2(n):
    """ recursive Fibonacci, employing memorization in a dictionary """
    if n in fib_dict:
        return fib_dict[n]
    else:
        fib_dict[n] = fibonacci2(n-1) + fibonacci2(n-2)
        # mutates fib_dict
    return fib_dict[n]
    

def fibonacci3(n):
    """ iterative Fibonacci, employing memorization in a list """
    if n <= 2:
        return 1
    else:
        fibb=[0 for i in range(n+1)]
        fibb[0] = fibb[1] = fibb[2] = 1  # initialize                       
        for k in range(3, n+1):
            fibb[k] = fibb[k-1] + fibb[k-2]  # update next element
        return fibb[n]

_cache = {1:1, 2:1}

def fib(n):
  if n not in _cache:
    _cache[n] = fib(n-1) + fib(n-2)
  return _cache[n]

def fibonacci4(n):
    """ fibonacci in O(1) memory """
    if n <= 2:
        return 1 # base case
    else:
        previous = 1
        current = 1
        for i in range(n-2): # n-2 iterations
            # simultaneous assignment
            current, previous = previous+current, current
        return current

def closed_fib(n):
    """ code for closed form Fibonacci number """
    return round(((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))