# minte9 LearnRemember

### Slow

In fibonacci function the bigger the argument, the longer the function runs. # 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

One solution is to keep track of values and store them in a dictionary. # 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


Last update: 61 days ago