Fibonacci Sequence

Iterative Version

In [25]:
def fib(n):
    a = 0
    b = 1
    i = 0
    
    while i < n:
        t = a + b
        a = b
        b = t
        i += 1
        print(a)
        
    return a
In [26]:
fib(5)
1
1
2
3
5
Out[26]:
5

Recursive Fibonacci (First attempt)

Asymptoic time complexity is on the order of $O(2^n)$

In [34]:
from rcviz import CallGraph, viz
In [35]:
cg = CallGraph()
In [36]:
@viz(cg)
def fib_rec_1(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_rec_1(n-1) + fib_rec_1(n-2)
In [37]:
fib_rec_1(5)
Out[37]:
5
In [38]:
cg
callviz: Rendering in inline in Jupyter Notebook
Out[38]:
nodes=15 140399005345616 fib_rec_1(5) ret: 5 140399004485568 fib_rec_1(4) ret: 3 140399005345616->140399004485568 1 (⇑9) 140399004486096 fib_rec_1(3) ret: 2 140399005345616->140399004486096 10 (⇑14) 140399007290144 fib_rec_1(3) ret: 2 140399004485568->140399007290144 2 (⇑5) 140399016469936 fib_rec_1(2) ret: 1 140399004485568->140399016469936 7 (⇑8) 140399007290672 fib_rec_1(2) ret: 1 140399007290144->140399007290672 3 (⇑3) 140399007291200 fib_rec_1(1) ret: 1 140399007290144->140399007291200 6 (⇑4) 140399005346912 fib_rec_1(1) ret: 1 140399007290672->140399005346912 4 (⇑1) 140399005347440 fib_rec_1(0) ret: 0 140399007290672->140399005347440 5 (⇑2) 140399007291728 fib_rec_1(1) ret: 1 140399016469936->140399007291728 8 (⇑6) 140399005347968 fib_rec_1(0) ret: 0 140399016469936->140399005347968 9 (⇑7) 140399016471040 fib_rec_1(2) ret: 1 140399004486096->140399016471040 11 (⇑12) 140399005348528 fib_rec_1(1) ret: 1 140399004486096->140399005348528 14 (⇑13) 140399004486624 fib_rec_1(1) ret: 1 140399016471040->140399004486624 12 (⇑10) 140399004487152 fib_rec_1(0) ret: 0 140399016471040->140399004487152 13 (⇑11)
In [41]:
def fib_rec_1a(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_rec_1a(n-1) + fib_rec_1a(n-2)
In [46]:
fib_rec_1a(50)
---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-46-3697af456c32> in <module>
----> 1 fib_rec_1a(50)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

<ipython-input-41-5baf06d76a9f> in fib_rec_1a(n)
      5         return 1
      6     else:
----> 7         return fib_rec_1a(n-1) + fib_rec_1a(n-2)

KeyboardInterrupt: 
In [44]:
# Global scope!
import sys
sys.getrecursionlimit()
Out[44]:
3000

Recursive Fibonacci (Second Attempt)

In [47]:
def fib_rec_2(n):
    # Nonlocal scope!
    
    def helper(a, b, i):
        # Local scope!
        if i == n:
            return b
        print(b)
        return helper(b, a+b, i+1)
    
    return helper(1, 0, 0)
In [48]:
fib_rec_2(50)
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
Out[48]:
12586269025