minte9
LearnRemember   PYTHON





Fibonacci 

 
# -------------------------------------
# FIBONACCI - SLOW version
# -------------------------------------
# We use recursion to get the Fibonacci sequence.
# The bigger the argument, the longer the function runs.
#
#    fb(0) = 0
#    fb(1) = 1
#    fb(n) = fb(n-1) + fb(n-2)

loops = 0
def fibonacci(n):
    global loops

    loops = loops + 1

    if n == 0: return 0
    if n == 1: return 1

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

fibonacci(30)
print ("Loops:", loops)  # Loops: 2692537

Fibonacci Dictionary (Memoization) 

 
# ------------------------------
# FIBONACCI - DICTIONARY version
# ------------------------------ 
# Keep track of values and store them in a dictionary. 
# This is called memoization.
# The algorithm is O(n).
#
#    fb(0) = 0
#    fb(1) = 1
#    fb(n) = fb(n-1) + fb(n-2)
#
# Fibonacci is naturally iterative.

def fibonacci(n):
    known = {0:0, 1:1}
    
    for i in range(2, n + 1):
        known[i] = known[i -1] + known[i -2]

    return known[n]


assert fibonacci(4) == 3  # 9
assert fibonacci(5) == 5  # 24
assert fibonacci(6) == 8  # 49

fibonacci(1000)  # works




References: