Collections / Efficiency
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
