def fib(n):
    #print(f'computing f({n})')
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

"""
Explanation: Memoization
This notebook discusses the technique of https://en.wikipedia.org/wiki/Memoization via the Fibonacci numbers.
The Fibonacci numbers $F_n$ are defined inductively for all $n\in\mathbb{N}$:
- $F_0 := 0$,
- $F_1 := 1$, and
- $F_{n+2} := F_{n+1} + F_n$ for all $n \in \mathbb{N}$.
The function fib takes a natural number $n$ as argument. The expression $\texttt{fib}(n)$ computes the $n$-th Fibonacci number $F_n$ in a naive way.
End of explanation
"""


import time

N  = 33
Ns = []
Ts = []
for n in range(22, N):
    start = time.time()
    Fn    = fib(n)
    #print(Fn)
    stop  = time.time()
    #print(f'elapsed time: {"{:.2e}".format(stop-start)}, fib({n}) = {Fn}')
    Ns.append(n)
    Ts.append(stop - start)

"""
Explanation: The problem with this definition of the function fib is that in order to compute e.g. $F_5$ we compute both $F_4$ and $F_3$.  However, in order to compute $F_4$, we compute $F_3$ and $F_2$.  Hence $F_3$ is computed twice.  Even worse, $F_2$ is computed twice for the two computations of $F_3$ and then it is also computed when computing $F_4$.  Hence, it is computed a total of $3$ times.  In general, it can be shown that when the above definition of fib is used to compute $F_n$, the number of times that $F_2$ needs to be computed grows as $\mathcal{O}\bigl(\varphi^n\bigr)$ where $\varphi = \frac{1}{2}\cdot\bigl(1 + \sqrt{5}\bigr)$.
End of explanation
"""


import matplotlib.pyplot as plt 

plt.plot(Ns, Ts)
plt.xlabel('n')
plt.ylabel('time')
plt.title('Time to compute fib(n).')
plt.show()

"""
Explanation: Let us plot the times.
End of explanation
"""


import math

Ts

LogTs = [math.log(t) for t in Ts]
plt.plot(Ns, LogTs)
plt.xlabel('n')
plt.ylabel('log(time)')
plt.title('Time to compute fib(n), logarithmic plot.')
plt.show()

for n in range(0, N-1):
    print(Ts[n]/Ts[n-1])

"""
Explanation: In order to verify that the running times are increasing exponentially, we plot the logarithms of the times.
End of explanation
"""


print((1+math.sqrt(5)) / 2)

"""
Explanation: Compare these ratios with the golden ratio 
$\phi = \frac{1}{2}\cdot\bigl(1 + \sqrt{5}\bigr)$:
End of explanation
"""


def memoize(f):
    Cache = {}
    
    def f_memoized(*args):
        if (f, args) in Cache:
            return Cache[(f, args)]
        result = f(*args)
        Cache[(f, args)] = result
        return result
    
    return f_memoized

fib = memoize(fib)

"""
Explanation: The function memoize takes a function f as its argument.  It returns a <em style="color:blue">memoized</em> version of the function f.  This memoized version will store all results in a cache and look them up instead of recomputing them.  
Note that the function object f_memoized that is returned by the function memoize is a so called 
closure.  The reason is that the variable
Cache, which is created in the scope where f_memoized is defined, is stored inside the function object
f_memoized.
End of explanation
"""


N  = 35
Ns = []
Ts = []
for n in range(1, N):
    start = time.time()
    Fn    = fib(n)
    stop  = time.time()
    Ns.append(n)
    Ts.append(stop - start)
    
plt.plot(Ns, Ts)
plt.xlabel('n')
plt.ylabel('time')
plt.title('Time to compute fib(n).')
plt.show()

"""
Explanation: Let's plot the times of the memoized version of fib.  This time, there should be no exponential increase.
End of explanation
"""


@memoize
def fib2(n):
    if n < 2:
        return n
    return fib2(n-2) + fib2(n-1)

N  = 35
Ns = []
Ts = []
for n in range(1, N):
    start = time.time()
    Fn    = fib2(n)
    stop  = time.time()
    Ns.append(n)
    Ts.append(stop - start)
    
plt.plot(Ns, Ts)
plt.xlabel('n')
plt.ylabel('time')
plt.title('Time to compute fib(n).')
plt.show()

"""
Explanation: We can achieve the same effect using a decorator:
End of explanation
"""


fib2.__closure__[0].cell_contents

"""
Explanation: Since fib2 is a closure, the dictionary Cache is stored inside fib2.  We can even inspect this dictionary manually.
End of explanation
"""


