<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 The Fibonacci Numbers
The Fibonacci numbers $F_n$ are defined by induction for all $n\in\mathbb{N}$
Step1:  It seems that the Fibonacci numbers grow pretty fast. Let us plot these numbers to get a better understanding of their growth.
Step2:  It looks like the Fibonacci numbers grow exponentially.  Let us confirm this hypothesis by plotting the logarithm of these numbers.
Step3:  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.
Step4:  The times seem to grow exponentially.
Step5:  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.
Step6:  The computation tree for the computation of fibonacci(6) shows the reason for the inefficiency
Step7:  Now it is even possible to compute the $100,000^\mbox{th}$ Fibonnaci number.
<ASSISTANT_TASK:>
Python Code:
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
<END_TASK>