MINTE9

2REMEMBER

Efficiency

 RunCode
def fibonacci(n):
    global loops
    loops += 1
    if n == 0: return 0
    if n == 1: return 1
    return fibonacci(n-1) + fibonacci(n-2)

loops = 0; print(fibonacci(4), loops)  # 3 9
loops = 0; print(fibonacci(5), loops)  # 5 15
loops = 0; print(fibonacci(6), loops)  # 8 25
loops = 0; print(fibonacci(30), loops)  # 832040 2692537
... 10 lines
˄˄˄

 RunCode
def fibonacci(n):

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

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

loops = 0; known = {0:0, 1:1}; print(fibonacci(4), loops)   # 3 7
loops = 0; known = {0:0, 1:1}; print(fibonacci(5), loops)   # 5 9
loops = 0; known = {0:0, 1:1}; print(fibonacci(6), loops)   # 8 11
loops = 0; known = {0:0, 1:1}; print(fibonacci(30), loops)  # 832040 59
... 11 lines
˄˄˄

 CompleteTask
"""
Write a function that reads words in words.txt and ...
store them in a dictionary

Use the in operator as a fast way to check
Compare the speed of impelemtation with the bisection search 

https://github.com/AllenDowney/ThinkPython2/blob/master/code/words.txt
https://gist.github.com/minte9/4c411d0c83cfdfa718085f792f810a18 """

# SOLUTION

# Dictionary search
     ???