RECURSION¶

def f(x):
    return x**2

f(4)

16

f(5)

25

f(-1)

1

f(1.2)

1.44

f("John")

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-9-4e27636d03a2> in <module>
----> 1 f("John")

<ipython-input-4-4261cf13ee74> in f(x)
      1 def f(x):
----> 2     return x**2

TypeError: unsupported operand type(s) for ** or pow(): 'str' and 'int'

# recursive solution to finding length
def length(xs):
    if xs == []:
        return 0
    else:
        return 1 + length(xs[1:])

length(['a','b',3])

3

#non-recursive length function
def length1(xs):
    result = 0
    for x in xs:
        result = result + 1
    return result

length1([1,2,3])

3

def factorial(n):
    if n < 0:
        return None
    elif n == 0:
        return 1
    else:
        return n*factorial(n-1)

print(factorial(20))

2432902008176640000

def sum_list_1(xs): # non-recursive
    result = 0
    for x in xs:
        result = result + x
    return result

sum_list_1([10,20,30])

60

def sum_list_2(xs): # recursive
    if xs == []:
        return 0
    else:
        return xs[0] + sum_list_2(xs[1:])

sum_list_2([10,20,30])

60

def max_list_1(xs):
    if xs == []:
        return None
    else:
        result = xs[0]
        for x in xs[1:]:
            if x > result:
                result = x
        return result

max_list_1([10,20,30])

30

def max_list_2(xs):
    if xs == []:
        return None
    elif len(xs) == 1:
        return xs[0]
    else:
        tail_max = max_list_2(xs[1:])
        if xs[0] > tail_max:
            return xs[0]
        else:
            return tail_max
        #max(xs[0], max_list_2(xs[1:]))

max_list_2([10,20,30])

30

max(10,20)

20

def fibonacci(n):
    # return the nth fibonacci number
    if n <= 0:
        return None
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)
    # this solution has repeated calculations which can be avoided by being clever (-:

fibonacci(6)

8

for (x,y) in zip([1,2,3],['John','Alice','Bob','David']):
    print(x,y)

1 John
2 Alice
3 Bob

def zipp1(xs,ys):
    result = []
    if len(xs) < len(ys):
        for i in range(len(xs)):
            result.append((xs[i],ys[i]))
    else:
        for i in range(len(ys)):
            result.append((xs[i],ys[i]))
    return result

zipp1([1,2,3,4,5],['John','Alice','Bob','David'])

[(1, 'John'), (2, 'Alice'), (3, 'Bob'), (4, 'David')]

def zipp2(xs,ys):
    if xs == [] or ys == []:
        return []
    else:
        return [(xs[0],ys[0])] + zipp2(xs[1:],ys[1:])

zipp2([1,2,3,4,5],['John','Alice','Bob','David'])

[(1, 'John'), (2, 'Alice'), (3, 'Bob'), (4, 'David')]

zipp2([2,3,4,5],['Alice','Bob','David'])

[(2, 'Alice'), (3, 'Bob'), (4, 'David')]

Quicksort¶

def partition(pivot,xs):
    small = []
    large = []
    for x in xs:
        if x <= pivot:
            small.append(x)
        else:
            large.append(x)
    return (small,large)

partition(20,[5,9,20,2,3,8,9,16])

([5, 9, 20, 2, 3, 8, 9, 16], [])

def quicksort(xs):
    if xs == []:
        return []
    else:
        pivot = xs[0]
        (small,large) = partition(pivot,xs[1:])
        return quicksort(small) + [pivot] + quicksort(large)

quicksort([5,9,20,2,3,8,9,16])

[2, 3, 5, 8, 9, 9, 16, 20]