Homework 9

Due Tuesday 31-Oct, at 10:00pm

To start

1. Create a folder named hw9
2. Create a new file hw9.py in that folder
3. Edit hw9.py and add the functions and some testcases as required
4. When you have completed and fully tested hw9, submit hw9.py to Gradescope. For this hw, you may submit up to 15 times, but only your last submission counts.

While you may submit to Gradescope as often as you like for this assignment, some questions are not autograded, so you will be responsible for testing your code and making sure it meets the problem requirements.

Some important notes

1. This homework is solo. You may not collaborate or discuss it with anyone outside of the course, and your options for discussing with other students currently taking the course are limited. See the academic honesty policy for more details.
2. After you submit to Gradescope, make sure you check your score. If you aren’t sure how to do this, then ask a CA or Professor.
3. There is no partial credit on Gradescope testcases for autograded problems. Your Gradescope score is your Gradescope score.
4. Read the last bullet point again. Seriously, we won’t go back later and increase your Gradescope score for any reason. Even if you worked really hard and it was only a minor error…
5. Do not hardcode the test cases in your solutions.
6. We are not giving you any starter code this week. That means you need to create your file from scratch and include your own testcases. For writing testcases, follow the style of testcases uses in the previous homeworks.
7. Remember the course’s academic integrity policy. Solving the homework yourself is your best preparation for exams and quizzes; cheating or short-cutting your learning process in order to improve your homework score will actually hurt your course grade long-term.

A Note About Style Grading

Like in the previous assignments, we will be grading your code based on whether it follows the 15-112 style guide. We may deduct up to 10 points from your overall grade for style errors. We highly recommend that you try to write clean code with good style all along, rather than fixing your style issues at the end. Good style helps you code faster and with fewer bugs. It is totally worth it. In any case, style grading already started, so please use good style from now on!

A few notes on recursion:

• You may (and in fact must) finally use recursion this week.
• The recursive problems require that you use recursion meaningfully in order to receive the points.
• You also may not use loops -- no for loops or while on the problems marked recursive.
• 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 upper, lower, 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). You may only use builtin functions or methods that are not O(1) only in the case that the input size is O(1) (one character, one element).

And even more important notes:

• You may not create large extraneous lists or otherwise store more information than what you need to solve the problem. For example, in maxEven(L) you cannot call evensOnly(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 maxEven(L) with recursion. In fact, that's the main point of asking you to solve both evensOnly(L) and maxEven(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).

1. Recursion-Only evenCount(L) [10 pts]
   Without using iteration, write the recursive function evenCount(L) which given a possibly-empty list L of integers, returns the number of even integers in L. So: evenCount([5,8,23,42]) returns 2.


2. Recursion-Only evenSum(L) [10 pts]
   Without using iteration, write the recursive function evenSum(L) which given a possibly-empty list L of integers, returns the sum of the even integers in L. Do not create a new list. You cannot use the builtin function sum of lists. Return 0 if the list has no even integers in it. So, evenSum([5,8,23,42]) returns 50.


3. Recursion-Only evensOnly(L) [10 pts]
   Without using iteration, write the recursive function evensOnly(L) which given a possibly-empty list L of integers, returns a new list containing only the even integers in L in the same order they appear in L. So, evensOnly([5,8,23,42]) returns [8, 42].


4. Recursion-Only maxEven(L) [15 pts]
   Without using iteration, write the recursive function maxEven(L) which given a possibly-empty list L of integers, returns the largest even integer in L, or None if L does not contain any even integers. So, maxEven([5,8,23,42]) returns 42.
5. recursive alternatingSum(L, n) [15 pts]
   Write the function alternatingSum(L, n) that takes a possibly-empty list of numbers, L, and returns the alternating sum of the list, where every nth value is subtracted rather than added. n will be always greater than 1. For example: alternatingSum([5,2,3,4,1,6], 2) returns 5-2+3-4+1-6 (that is, -3).
   alternatingSum([5,2,3,4,1,6], 3) returns 5+2-3+4+1-6 (that is, 3). If L is empty, return 0.


6. recursive capitalizeWords(wordList) [20 pts]
   Write a recursive function that takes a list of words and returns a list that contains all the words capitalized. For example,
   assert(capitalizeWords(['foo', 'bar', 'world', 'hello']) == ['FOO', 'BAR', 'WORLD', 'HELLO'])
   Your solution should not use any loops; you must solve the problem using recursion. Your solution should not use any functions that imply iteration. In particular, the use of upper() for strings is forbidden if the string has more than one character. You may use O(N) string builtin functions as long as the string consists of one character. This means, you can use s.upper() only if len(s) == 1. If you do, the autograder or a manual check later will reject your solution.


7. drawFractalSun(xc, yc, r, level) [20 pts, manually graded]
   Write a function that draws a majestic fractal sun. The fractal sun is composed of a circle of radius r, and 8 rays of length 2*r originating from the center of the circle and radially equally spaced. The external tip of each ray is also the origin of a recursively downsized fractal sun with radius equal to 1/4 of the radius of the sun at the previous level. Also, the suns originating at the tip of the rays will have different colors, i.e., the color of a sun is a function of the recursion level of the fractal sun itself. You can invent the coloring function you prefer, just make sure that your sun will look good no matter what the maximum level of recursion is going to be. Your fractal sun will be generated by a recursive function drawFractalSun(xc, yc, r, level) which you will write. Your function will take as parameter a canvas to draw on, the (xc, yc) coordinates of the center of the sun, the radius r of the sun's circle, and an integer level representing the maximum depth of recursion of your fractal sun. Note: In this task, you can use iteration to draw the rays. The following picture shows a fractal sun with a maximum recursion depth of 1, 2, and 4, with colors alternating from red, green, and blue.
   

   

   

   

   
   The following picture shows a fractal sun with a maximum recursion depth of 5, with colors fading from yellow to red.
   
   Your solution should use cmu_graphics. Do not call runApp in the submitted code. Otherwise, the autograder might fail.