Python 3.2.5 (default, May 15 2013, 23:07:10) [MSC v.1500 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 


#Running the recursive binom 
#(its time complexity is exponential, therefore binom(50,25) would take a lot of time to compute)


>>> binom(50,25)
Traceback (most recent call last):
  File "<pyshell#0>", line 1, in <module>
    binom(50,25)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    return binom(n-1,k) + binom(n-1,k-1)
  File "C:/Personal/Teaching/CS-intro/2015a/Recitations/7/binom_mon.py", line 6, in binom
    def binom(n, k):
KeyboardInterrupt
>>> 
>>> 
>>> 
>>> 

# running the recursive binom on small inputs

>>> binom(4,2)
6
>>> ================================ RESTART ================================


#binom with memoization

>>> 
>>> binom_fast(4,2)
6


# Its complexity is polynomial in k,n - much faster than the basic recursive implementation

>>> binom_fast(50,25)
126410606437752
>>> 


# adding trace.
# (n=2, k=1) is computed recursively only once. 
# In the second time this value is needed it is taken from the dictionary.

>>> binom_fast_trace(4,2)
>>(4,2)
>>>>(3,2)
>>>>>>(2,2)
<<<<<<(2,2)
>>>>>>(2,1)
>>>>>>>>(1,1)
<<<<<<<<(1,1)
>>>>>>>>(1,0)
<<<<<<<<(1,0)
<<<<<<(2,1)
<<<<(3,2)
>>>>(3,1)
>>>>>>(2,1)
<<<<<<(2,1)
>>>>>>(2,0)
<<<<<<(2,0)
<<<<(3,1)
<<(4,2)
6
>>>