

In [9]:

    
import numpy as np

Problem 1: recursive add function



In [3]:

    
def recursive_add(a, b):
    if b == 0:
        return a
    else:
        return 1 + recursive_add(a, b-1)



In [8]:

    
assert recursive_add(2, 3) == 5
assert recursive_add(0, 0) == 0
assert recursive_add(1, 1) == 2
assert recursive_add(10, 12) == 22

Problem 2: recursive average function



In [62]:

    
def recursive_avg(array):
    n = len(array)
    if n == 1:
        return array[0]
    elif n == 2:
        return (array[0] + array[1]) / 2.0
    else:
        return (array[n-1] + (n-1) * recursive_avg(array[0:n-1])) / n



In [63]:

    
for a in [np.arange(10), np.ones(15), np.zeros(4), np.array([5]), np.array([1, 17.2])]:
    assert recursive_avg(a) == np.mean(a)

Problem 3: Ackerman's



In [122]:

    
def a(m, n):
    if m == 0:
        print 'a({}, {}) = {}'.format(m, n, n+1)
        return n + 1
    elif (m != 0) and (n == 0):
        print 'a({}, {}) = a({}, {})'.format(m, n, m-1, 1)
        return a(m-1, 1)
    else:
        print 'a({}, {}) = a({}, a({}, {}))'.format(m, n, m-1, m, n-1)
        return a(m-1, a(m, n-1))



In [123]:

    
a(2, 2)









    



a(2, 2) = a(1, a(2, 1))
a(2, 1) = a(1, a(2, 0))
a(2, 0) = a(1, 1)
a(1, 1) = a(0, a(1, 0))
a(1, 0) = a(0, 1)
a(0, 1) = 2
a(0, 2) = 3
a(1, 3) = a(0, a(1, 2))
a(1, 2) = a(0, a(1, 1))
a(1, 1) = a(0, a(1, 0))
a(1, 0) = a(0, 1)
a(0, 1) = 2
a(0, 2) = 3
a(0, 3) = 4
a(0, 4) = 5
a(1, 5) = a(0, a(1, 4))
a(1, 4) = a(0, a(1, 3))
a(1, 3) = a(0, a(1, 2))
a(1, 2) = a(0, a(1, 1))
a(1, 1) = a(0, a(1, 0))
a(1, 0) = a(0, 1)
a(0, 1) = 2
a(0, 2) = 3
a(0, 3) = 4
a(0, 4) = 5
a(0, 5) = 6
a(0, 6) = 7






    Out[123]:





7

Problem 5: GCD



In [90]:

    
def gcd(x, y):
    if (y <= x) and (x % y == 0):
        return y
    elif (x < y):
        return gcd(y, x)
    else:
        return gcd(y, x%y)



In [95]:

    
gcd(20, 10)









    Out[95]:





10

Problem 6: recursive fibbonacci



In [64]:

    
def gfib(f0, f1, n):
    if n == 0:
        return f0
    elif n == 1:
        return f1
    else:
        return gfib(f0, f1, n-1) + gfib(f0, f1, n-2)



In [72]:

    
gfib(0, 1, 6)









    Out[72]:





8

Self Check



In [75]:

    
def M(x, y):
    print x, y
    if x == y:
        return x
    elif y > x:
        return M(x, y-x)
    elif x > y:
        return M(x-y, y)



In [80]:

    
M(20, 10)