CMU 15-112: Fundamentals of Programming and Computer Science
Homework 12 (Due Wednesday 4-Aug at 5pm ET)
- Create a folder named 'hw12'
- Download all of these to that folder:
- Edit hw12.py
- When you have completed and fully tested hw12, submit hw12.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.
A few more notes:
- You may (and in fact must) finally use recursion this week.
- Every problem this week requires that you use recursion meaningfully in order to receive the points. We may manually review this.
- You also may not use loops -- no
for
loops orwhile
loops this week! - You may use helper functions, so long as they are not iterative.
- You may use wrapper functions -- that is, your solution function may itself be a non-recursive (but also non-iterative) wrapper around a recursive helper function.
- You may only use builtin functions or methods if they run in O(1). So in particular, among many other builtins you may not use this week, you may not use sum, sort, sorted, min, or max this week (you can write your own recursive versions of these if you wish, though that is not required, and we did not do that for our sample solutions). Also, note that slicing (L[i:j]) is just fine this week.
Homework 12 Overview:
- Recursion-Only oddCount(L) [15 pts]
- Recursion-Only oddSum(L) [15 pts]
- Recursion-Only oddsOnly(L) [15 pts]
- Recursion-Only maxOdd(L) [15 pts]
- Recursion-Only hasConsecutiveDigits(n) [20 pts]
- Recursion-Only alternatingSum(L) [20 pts]
- Bonus/Optional: Recursion-Only Recursive Tetris! [3 pts]
- Recursion-Only oddCount(L) [15 pts] [autograded]
Without using iteration, write the recursive function oddCount(L) which given a possibly-empty list L of integers, returns the number of odd integers in L. - Recursion-Only oddSum(L) [15 pts] [autograded]
Without using iteration, write the recursive function oddSum(L) which given a possibly-empty list L of integers, returns the sum of the odd integers in L. Do not create a new list. Return 0 if the list has no odd integers in it. - Recursion-Only oddsOnly(L) [15 pts] [autograded]
Without using iteration, write the recursive function oddsOnly(L) which given a possibly-empty list L of integers, returns a new list containing only the odd integers in L in the same order they appear in L. - Recursion-Only maxOdd(L) [15 pts] [autograded]
Without using iteration, write the recursive function maxOdd(L) which given a possibly-empty list L of integers, returns the largest odd integer in L, or None if L does not contain any odd integers. - Recursion-Only hasConsecutiveDigits(n) [20 pts] [autograded]
Without using iteration, write the recursive function hasConsecutiveDigits(n) that takes a possibly-negative int value n and returns True if that number contains two consecutive digits that are the same, and False otherwise.
def testHasConsecutiveDigits(): print("Beginning hasConsecutiveDigits test cases...") assert(hasConsecutiveDigits(1123) == True) assert(hasConsecutiveDigits(-1123) == True) assert(hasConsecutiveDigits(1234) == False) assert(hasConsecutiveDigits(0) == False) assert(hasConsecutiveDigits(1233) == True) print("Passed!")
- Recursion-Only alternatingSum(L) [20 pts] [autograded]
Without using iteration, write the function alternatingSum(L) that takes a possibly-empty list of numbers, and returns the alternating sum of the list, where every other value is subtracted rather than added. For example: alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3). If L is empty, return 0. - Bonus/Optional: Recursion-Only Recursive Tetris! [3 pts] [manually graded]
For bonus this week, submit a new entirely-recursive version of Tetris to hw12-bonus (a separate assignment on autolab). You may start from the Tetris code you submitted for hw9, but then convert it to be entirely recursive. No loops, and no built-ins unless they run in O(1)!