- Trace #1:
def ct1(lst, depth=0):
print(depth, "in:", lst)
if len(lst) == 0:
result = []
elif lst[0] % 2 == 0:
result = ct1(lst[1:], depth + 1)
else:
result = [lst[0]]
result += ct1(lst[1:], depth + 1)
print(depth, "out:", result)
return result
ct1([7, 40, 33])
- Trace #2:
def ct2(s, d=0):
print(d, "in: ", s)
if len(s) == 0:
res = ""
else:
res = s[::2] + ct2(s[1::2], d + 1)
print(d, "out: ", res)
return res
ct2("abcdefgh")
- Code #3:
def ct3(a):
if len(a) == 0 or len(a) == 1:
return 0
print(a)
if a[0] == a[1]:
return ct3(a[2:])
else:
return 1 + ct3(a[1:])
print(ct3("tools"))
- Code #4:
def fRetG(x):
print("fRetG")
return x // 2
def myFunc(x):
print(x)
if x < 0:
return 0
elif x == 1:
return 1
else:
return x + myFunc(x - 5)
def ct4(x):
print("ret=", myFunc(fRetG(x)))
ct4(16)
- Code #5:
def ct5(L):
print("in:", L)
if len(L) == 1:
r = L[0]
else:
m = len(L) // 2
v1 = ct1(L[:m])
v2 = ct1(L[m:])
if v1 > v2:
r = v1
else:
r = v2
print("out:", r)
return r
print(ct5([58, 17, 40, 86]))
- multiply(a,b)
Write a recursive function called multiple(a,b), that returns the value a * b. You can only use + and – operators in
this function.
- bunnyEars(n)
We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even
bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot. Recursively return the number of
"ears" in the bunny line.
assert(bunnyEars2(0) == 0)
assert(bunnyEars2(1) == 2)
assert(bunnyEars2(2) == 5)
- equals(a,b)
Write a recursive function called equals, that takes two lists as input and returns true if the two lists are the
same, otherwise it should return false. You can assume that both lists will always be the same size. You cannot
use any lists functions including len.
- onlyOddDigits(L)
This function must be written recursively. A solution that uses loops, comprehensions, generators, or iterative
built-in functions such as range will not be accepted.
Without using strings, write the recursive function onlyOddDigits(L), that takes a list L of non-negative
integers (you may assume that), and returns a new list of the same numbers only without their even digits (if that
leaves no digits, then replace the number with 0). So: onlyOddDigits([43, 23265, 28, 58344]) returns
[3, 35, 0, 53]. Also the function returns the empty list if the original list is empty. Remember to not use strings.
- recursiveVowelCount(s)
Do not use loops, iteration, list/string functions that imply iteration (e.g., count, len) or try/except on this problem.
Implement the function recursiveVowelCount(s) which takes a string s, and returns the number of vowels in s. You can assume
that s only contains lowercase characters and non-alphabetical characters. The vowels are "a", "e", "i", "o", and "u".
So, for example:
assert(recursiveVowelCount("abc def a yzyzyz") == 3) # two a's and one e
assert(recursiveVowelCount("hello") == 2) # one e and one o
assert(recursiveVowelCount("bcd") == 0) # no vowels
- removeVowels(s)
Write the non-destructive function removeVowels(s) which takes a string, s, and returns a copy of it with all of
the vowels removed. For example, removeVowels("Hello there") returns "Hll thr". This function must be written
recursively. A solution that uses loops, comprehensions, generators, or iterative built-in functions such as
range will not be accepted.
- reverse(s)
Write the function reverse(s) using recursion (no loops fancy slicing!) in two different ways:
- Head and tail (reverse characters 1 to n-1, then put the first one at the end)
"abcd" --> "a" "dcb" --> "dcba"
- Split down the middle aka "divide and conquer" (reverse each half and combine)
"abcd" --> "ba" "dc" --> "dcba"
- getHiLo(lst)
Write the recursive function getHiLo(lst) which, given a list of integers lst returns a tuple contain the highest
and lowest values in the list. For example:
assert(getHiLo([1, 7, 3, 8, 2, 9, 6, 4, 5]) == (9,1))
assert(getHiLo([5]) == (5,5))
assert(getHiLo([]) == None)
Your solution must use recursion. If you use any loops, comprehensions, or iterative functions, it will not be accepted.
- Recursive permutations
Write a function that takes a list with n elements and returns a list containing all permutations of these n elements
assert(permutations([1,2,3]) == [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]])
In this problem, you are allowed to use a loop, but your solution must still be meaningfully recursive.
- wordCounter(wordList,word)
This function must be written recursively. A solution that uses loops, comprehensions, generators, or iterative
built-in functions such as range will not be accepted. Note that the built-in Python function count is iterative, so you can’t use it.
Write the recursive function wordCounter(wordList,word) which,given a list of words and a word, returns
how many times word appears in the list. For example, the following code:
wordList=["father","bless","of","golf","of","golf","father","of"]
print(wordCounter(wordList,"of"))
print(wordCounter(wordList,"golf"))
print(wordCounter(wordList,"fred"))
prints 3 2 0