Homework 9

Due Tuesday 22-Mar, at 10:00pm

To start

Create a folder named hw9
Create a new file hw9.py in that folder
Edit hw9.py and add the functions and some testcases as required
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

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.
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.
There is no partial credit on Gradescope testcases for autograded problems. Your Gradescope score is your Gradescope score.
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…
Do not hardcode the test cases in your solutions.
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.
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 if they don't iterate over something. 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).

Problems

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.

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

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

Recursive maxEven(L) [10 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. You can't use the builtin function max.

Recursive capitalizeWords(wordList) [10 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.

Recursive onlyEvenDigits(L) [15 pts]
Without using iteration and without using strings, write the recursive function onlyEvenDigits(L), that takes a list L of non-negative integers (you may assume that), and returns a new list of the same numbers only without their odd digits (if that leaves no digits, then replace the number with 0). So: onlyEvenDigits([43, 23265, 17, 58344]) returns [4, 226, 0, 844]. Also the function returns the empty list if the original list is empty. Remember to not use strings. You may not use loops/iteration in this problem.

Hint: We wrote a recursive helper function onlyEvens(n) that takes an integer n and returns the same integer but with all the odd digits removed. So onlyEvens(1234) returns 24.

Recursive alternatingSum(L) [15 pts]
Write the function alternatingSum(L) that takes a possibly-empty list of numbers, L, 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 lst is empty, return 0.

Recursive drawFractalHTree() [20 pts] [manually graded]
Write a program that draws a fractal H-tree. Our fractal H-tree is composed of a line of length d, and 2 smaller lines of length d divided by √2 originating from each end point. The end points of each of the smaller lines are also the origin of a recursively downsized fractal h-tree with length equal to half of the length of the h-tree at the previous level. The width of the lines should gradually decrease as well (make reasonable choices). Your fractal h-tree will be generated by a function drawFractalHTree(canvas, xc, yc, d, color, 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 h-tree, the length d of the horizontal line, a color, and an integer level representing the maximum depth of recursion of your fractal h-tree. The following picture shows a fractal h-tree with a maximum recursion depth of 2 with color blue.

The following picture shows a fractal h-tree with a maximum recursion depth of 6 with color blue.