Homework 9 (Due Saturday 5-Nov at 8pm ET)

Important Notes:

Read the "Important Notes" at the top of hw1. The same general rules apply to this hw regarding solo, sample solution videos, etc.
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.
You will need these starter files:
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.
As always, all your functions must be non-destructive unless the problem specifically indicates otherwise.
Also, if Python happens to provide a function or method that basically outright solves a problem, do not it. Naturally, we are looking for you to write the core logic of the problem.

Additional Notes for Recursion Homework:

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.

And even more important notes:

You may not use strings for numeric problems. For example, you should not convert n to a string in hasConsecutiveDigits(n).
You may not create large extraneous lists or otherwise store more information than what you need to solve the problem. 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.
You may not destructively modify arguments unless the problem explicitly says you should.
Your functions may not be extremely slow. You do not need to find the absolute best algorithm in most cases, but it must run reasonably quickly (i.e. if your non-graphics code takes ten seconds to pass our test cases, there is likely another approach you should consider).

This homework is slightly lighter than usual so that you can enjoy Hack112! Relatedly, we will have lighter OH support on Saturday, so we recommend you start early.

Attend a miniLecture [5 pts]
Recursion-Only oddCount(L) [10 pts]
Recursion-Only oddSum(L) [10 pts]
Recursion-Only oddsOnly(L) [10 pts]
Recursion-Only maxOdd(L) [10 pts]
Recursion-Only hasConsecutiveDigits(n) [15 pts]
Recursion-Only alternatingSum(L) [20 pts]
Recursion-Only Freddy Fractal Viewer [20 pts]
Bonus/Optional: Recursion-Only Recursive Tetris! [4 pts]

Attend a TA-led miniLecture [5 pts] [manually graded]
Attend one of the TA-Led Mini-Lectures. These are separate from recitations, small-groups, large-groups, optional exploratory sessions, etc. See the course schedule for a list of your many fine options to attend. Also, look to Piazza for descriptions and additional information. As always, 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.

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.

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.

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.

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.

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

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.

Recursion-Only Freddy Fractal Viewer [20 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. You do not need not be pixel-perfect with the facial features; just 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 following figure shows an example of a Fractal Teddy with maximum recursion level (depth) of 5.

Hints:
- The radius of each ear is exactly half the radius of the face.
- The center of each ear is exactly at the top corner of the bounding box around the face. In the image below, we've drawn an extra square and a 45-degree line to illustrate this.
- To draw the mouth, you should use the function canvas.create_arc(...) of Tkinter with the optional parameters style and extent. Try running the code below to understand how this works. (For more information about this function read the documentation here.)
```
from cmu_112_graphics import *
import math

def redrawAll(app, canvas):
    cx = app.width / 2
    cy = app.height / 2
    x0 = cx - 100
    x1 = cx + 100
    y0 = cy - 50
    y1 = cy + 50
    e = -180
    canvas.create_rectangle(x0, y0, x1, y1, outline = 'red')
    canvas.create_oval(x0, y0, x1, y1, outline = 'blue')
    canvas.create_arc(x0, y0, x1, y1,
                        outline="green", width = 5, style="arc", extent=e)

runApp(height = 400, width = 400)
```
Finally, just for fun, the following is not a Freddy Fractal, but it's an interesting (if perhaps somewhat creepy) related fractal animated gif that we found lurking somewhere on the web:

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 an earlier hw, 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!