CMU 15-112: Fundamentals of Programming and Computer Science
Homework 9 (Due Saturday 30-Oct at 8pm ET)
(Optional Early Bird Bonus for Part A is Due Thu 28-Oct at 10pm ET)

Important Notes:

1. Read the "Important Notes" at the top of hw1. The same general rules apply to this hw regarding solo, early-bird bonus, sample solution videos, etc.
2. Specifically, Friday Lab is optional this week for those who receive the early-bird bonus.
3. This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
4. You will need these starter files:
   1. hw9.py
   2. cs112_f21_week9_linter.py
5. For this hw, you may submit up to 5 times to the early-bird submission and up to 5 more times for the main hw submission, but only your last submission counts.
6. Do not hardcode the test cases in your solutions.
7. As always, all your functions must be non-destructive unless the problem specifically indicates otherwise.
8. Also, if Python happens to provide a function that basically outright solves a problem, such as statistics.median() for the median problem in hw4, do not use that function. Naturally, we are looking for you to write the core logic of the problem.

Additional Notes for Recursion Homework:

1. You may (and in fact must) finally use recursion this week.
2. Every problem this week requires that you use recursion meaningfully in order to receive the points.
3. You also may not use loops -- no for loops or while loops this week!
4. You may use helper functions, so long as they are not iterative.
5. 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.
6. 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.

And even more important notes:
Basically, all the standard 112 restrictions still apply here:

1. You may not use strings for numeric problems. For example, you should not convert n to a string in hasConsecutiveDigits(n).
2. You may not gratuitously create large extraneous lists or otherwise be needlessly wasteful. For example, in maxOdd(L) you cannot call oddsOnly(L) and then take the max of that list, since that gratuitously creates an extraneous list (and, to be technical, uses O(N) space instead of O(1) space as the problem requires). Instead, directly compute maxOdd(L) with recursion. In fact, that’s the main point of asking you to solve both oddsOnly(L) and maxOdd(L): to encourage you to think about the structural differences in these problems and how that affects your recursive logic.
3. You may not destructively modify arguments unless the problem explicitly says you should.
4. You may not use gratuitously slow algorithms. You do not need to find the absolute best algorithm in most cases, but it must run reasonably quickly (within broad reason).

---

Part A:

1. Recursion-Only oddCount(L) [7.5 pts]
2. Recursion-Only oddSum(L) [7.5 pts]
3. Recursion-Only oddsOnly(L) [7.5 pts]
4. Recursion-Only maxOdd(L) [7.5 pts]

Part B:

5. Friday Lab [10 pts]
6. Recursion-Only hasConsecutiveDigits(n) [15 pts]
7. Recursion-Only alternatingSum(L) [15 pts]
8. Recursion-Only Freddy Fractal Viewer [30 pts]
9. Bonus/Optional: Recursion-Only Recursive Tetris! [4 pts]

---

Part A:

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

---

Part B:

5. Friday Lab [10 pts]
   Attend your Friday lab (in your assigned recitation time). To receive full credit, you must show up on time, stay the whole time, be focused and uni-tasking (not multi-tasking), and fully participating. Note that if you received the Early Bird Bonus, you are excused from attending Friday lab, though you are still most welcome to attend.


6. 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!")
   



7. 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.


8. 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.
   
   


9. 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. Note: if you do the Tetris bonus, please print 'hit t for tetris bonus' to the console when we run your Freddy Fractal Viewer. And have fun!

---