MINTE9

REMEMBERS

Slow

 
# Slow (recursion)
#
#    fb(0) = 0
#    fb(1) = 1
#    fb(n) = fb(n-1) + fb(n-2)
#
# The bigger the argument, the longer the function runs.
# It gets worst as the argument gets bigger.

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)

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

fibonacci(30)
print (loops) # 2692537 - Look Here

Fast

 
# Fast (recursion & dictionary)
#
#    fb(0) = 0
#    fb(1) = 1
#    fb(n) = fb(n-1) + fb(n-2)
#
# To make the algorith run faster ...
# one solution is to keep track of values and store them in a dictionary.

loops = 0
known = {0:0, 1:1}

def reset():
    loops = 0
    known = {0:0, 1:1}

def fibonacci(n):

    global loops; 
    loops = loops + 1
    
    if n in known: 
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

reset(); assert fibonacci(4) == 3;           print (loops) # 7
reset(); assert fibonacci(5) == 5;           print (loops) # 10
reset(); assert fibonacci(6) == 8;           print (loops) # 13

fibonacci(1000)
print (loops) # 2002 - Look Here