CMU 15-112: Fundamentals of Programming and Computer Science
Week 4: Recursion

To start:
1. In the folder named 'Week4'
2. Download 11. recursionPractice.py
3. Edit the downloaded file using your preferred editor
Do not use recursion in the solutions.

Code Tracing

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]))

Free Response

multiply(a,b)
Write a recursive function called multiply(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 list 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 or fancy slicing!) in two different ways:
1. Head and tail (reverse characters 1 to n-1, then put the first one at the end) "abcd" --> "a" "dcb" --> "dcba"
2. 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 containing 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