CMU 15-112: Fundamentals of Programming and Computer Science
Homework 10 (Due Saturday 10-Apr at 5pm ET)

To start:

1. Create a folder named 'week10'
2. Download all of these to that folder:
   • hw10.py
   • cs112_s21_week10_linter.py
3. Edit hw10.py
4. When you have completed and fully tested hw10, submit hw10.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.

Do not hardcode the test cases in your solutions.

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.
• You also may not use loops -- no for loops or while 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 9 Overview:

1. Recursion-Only oddCount(L) [10 pts]
2. Recursion-Only oddSum(L) [10 pts]
3. Recursion-Only oddsOnly(L) [10 pts]
4. Recursion-Only maxOdd(L) [10 pts]
5. Recursion-Only hasConsecutiveDigits(n) [15 pts]
6. Recursion-Only alternatingSum(L) [15 pts]
7. Recursion-Only Freddy Fractal Viewer [30 pts]
8. Bonus/Optional: Recursion-Only Recursive Tetris! [4 pts]

---

1. Recursion-Only oddCount(L) [10 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.


2. Recursion-Only oddSum(L) [10 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.


3. Recursion-Only oddsOnly(L) [10 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.


4. Recursion-Only maxOdd(L) [10 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.


5. Recursion-Only hasConsecutiveDigits(n) [15 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!")
   



6. Recursion-Only alternatingSum(L) [15 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.


7. Recursion-Only Freddy Fractal Viewer [30 pts] [manually graded]
   Following the Fractal Viewer pattern in the course notes here, write a fractal that draws a circular-shaped face of a teddy bear (named "Freddy"!), without ears. While you need not be pixel-perfect, try to make the face reasonably similar to the one in the image below.
   
   At level 0, you get one freddy without ears. At level 1, the ears of the outer freddy themselves become freddies. And so on.
   
   The radius of each ear is exactly half the radius of the face. The following figure shows an example of a Fractal Teddy with maximum recursion level (depth) of 5.
   
   
   
   Hint: to draw the mouth, you should use the function create_arc(...) of Tkinter with the optional parameters style and extent. For more information about this function read the documentation here.
   
   


8. Bonus/Optional: Recursion-Only Recursive Tetris! [4 pts] [manually graded]
   For bonus this week, add a feature to your Freddy Fractal Viewer that when the user presses 't', it converts into the game of Tetris. You may start from the Tetris code you submitted for hw8, but then convert it to be entirely recursive. Fun!

---