def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

[ (n,fibonacci(n)) for n in range(19) ]

"""
Explanation: The Fibonacci Numbers
The Fibonacci numbers $F_n$ are defined by induction for all $n\in\mathbb{N}$:
  - $F_0 := 0$,
  - $F_1 := 1$, 
  - $F_{n+2} = F_{n+1} + F_n$ for all $n \in \mathbb{N}$.
Given a natural number n, the function fibonacci(n) computes the number $F_n$.
End of explanation
"""


import matplotlib.pyplot as plt
import seaborn           as sns

m = 34
X = []
Y = []
for n in range(m):
    X.append(n)
    Y.append(fibonacci(n))
sns.set_style('darkgrid')
plt.figure(figsize=(15, 10))
plt.plot(X, Y, 'bo')
plt.xticks(X)
plt.yticks([y * 2e5 for y in range(19)])
plt.xlabel('n')
plt.ylabel('F(n)')
plt.title('The Fibonacci Numbers')
plt.show()

"""
Explanation: It seems that the Fibonacci numbers grow pretty fast. Let us plot these numbers to get a better understanding of their growth.
End of explanation
"""


import math

X = X[1:]
Y = Y[1:]
logY = [math.log(y) for y in Y]
sns.set_style('darkgrid')
plt.figure(figsize=(15, 10))
plt.plot(X, logY, 'bo') 
plt.xticks(X)
plt.yticks(list(range(17)))
plt.xlabel('n')
plt.ylabel('ln(F(n))')
plt.title('The Logarithms of the Fibonacci Numbers')
plt.show()

"""
Explanation: It looks like the Fibonacci numbers grow exponentially.  Let us confirm this hypothesis by plotting the logarithm of these numbers.
End of explanation
"""


import time

m = 36
Y = []
X = list(range(m))
for n in range(m):
    start = time.time()
    print(f'fib({n}) = {fibonacci(n)}')
    stop  = time.time()
    print(stop - start)
    Y.append(stop - start)
    
sns.set_style('darkgrid')
plt.figure(figsize=(15, 10))
plt.plot(X, Y, 'bo') 
plt.xticks(X)
plt.xlabel('n')
plt.ylabel('time in seconds')
plt.title('Time to Compute the Fibonacci Numbers')
plt.show()

"""
Explanation: This plot looks linear and confirms our hypothesis that these numbers grow exponentially.
Computing the Fibonacci numbers took quite long.  Lets measure these times and plot them.
End of explanation
"""


m = 36
Y = []
X = list(range(20, m))
for n in X:
    start = time.time()
    fibonacci(n)
    stop  = time.time()
    Y.append(math.log(stop - start))
    
sns.set_style('darkgrid')
plt.figure(figsize=(15, 10))
plt.plot(X, Y, 'bo') 
plt.xticks(X)
plt.xlabel('n')
plt.ylabel('time in seconds')
plt.title('Logarithm of the Time to Compute the Fibonacci Numbers')
plt.show()

"""
Explanation: The times seem to grow exponentially.
End of explanation
"""


import graphviz as gv

class ComputationTree:
    def __init__(self, arg, value, left=None, right=None):
        self.mArg   = arg
        self.mValue = value
        self.mLeft  = left
        self.mRight = right

def isLeaf(self):
    return self.mLeft == None and self.mRight == None

ComputationTree.isLeaf = isLeaf
del isLeaf

def toDot(self):
    ComputationTree.sCounter = 0 # static variable of the class ComputationTree
    dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
    NodeDict = {}
    self._assignIDs(NodeDict)
    for n, t in NodeDict.items():
        dot.node(str(n), label='{' + str(t.mArg) + '|' + str(t.mValue) + '}')
        if t.mLeft != None and t.mRight != None:
            dot.edge(str(n), str(t.mLeft .mID))
            dot.edge(str(n), str(t.mRight.mID))
    return dot

ComputationTree.toDot = toDot
del toDot

def _assignIDs(self, NodeDict):
    ComputationTree.sCounter += 1
    self.mID = ComputationTree.sCounter
    NodeDict[self.mID] = self
    if self.isLeaf():
        return
    self.mLeft ._assignIDs(NodeDict)
    self.mRight._assignIDs(NodeDict)
    
ComputationTree._assignIDs = _assignIDs
del _assignIDs

def fibonacci_tree(n):
    if n <= 1:
        return ComputationTree(n, n)
    C1 = fibonacci_tree(n-1)
    C2 = fibonacci_tree(n-2)
    return ComputationTree(n, C1.mValue + C2.mValue, C1, C2)

t = fibonacci_tree(6)
t.toDot()

"""
Explanation: The logarithmic plot confirms this.  In order to investigate the reason for this exponential growth, we compute the computation tree.  This tree shows the recursive invocations of the function.
End of explanation
"""


def fibonacci_mem(n):
    if n <= 1:
        return n
    L    = [0 for k in range(n+1)]
    L[0] = 0
    L[1] = 1
    for k in range(2, n+1):
        L[k] = L[k-1] + L[k-2]
    return L[n]

"""
Explanation: The computation tree for the computation of fibonacci(6) shows the reason for the inefficiency:
* fibonacci(5) is computed once,
* fibonacci(4) is computed 2 times,
* fibonacci(3) is computed 3 times,
* fibonacci(2) is computed 5 times,
* fibonacci(1) is computed 8 times, and
* fibonacci(0) is computed 5 times.
If we want to compute the Fibonacci numbers efficiently, we must not compute the value fibonacci(n) for a given n more than once.  The easiest way to achieve this is by storing the Fibnacci numbers in a list L.  In the implementation below, L[n] stores the $n$-th Fibonacci number.
End of explanation
"""


%%time
x = fibonacci_mem(100000)

x

"""
Explanation: Now it is even possible to compute the $100,000^\mbox{th}$ Fibonnaci number.
End of explanation
"""


