GrPA 1
def reverse(L):
if len(L) <= 1:
return L
# Bring the last element to the front
# And reverse the first n - 1 elements
return [L[-1]] + reverse(L[:-1])
GrPA 2
def linear(P, Q, k):
if len(P) != len(Q):
return False
if len(P) == 0:
return True
if P[0] / Q[0] != k:
return False
return linear(P[1: ], Q[1: ], k)
GrPA 3
def collatz(n):
# base case of the recursion
# if n = 1, you don't need to call the function at all
if n == 1:
return 0
# simple application of the piecewise defn of the
# Collatz function
if n % 2 == 0:
return 1 + collatz(n // 2)
else:
return 1 + collatz(3 * n + 1)
GrPA 4
def steps(n):
if n == 1:
return 1
if n == 2:
return 2
if n == 3:
return steps(1) + steps(2) + 1
return steps(n - 1) + steps(n - 2) + steps(n - 3)
GrPA 5
def ancestry(P, present, past):
if present == past:
return [past]
return [present] + ancestry(P, P[present], past)