Start by downloading the project skeleton pp1.zip. It contains two files, recursion.py, and test.py.

Your task is to fill in the three missing functions in recursion.py. You can run this file directly by saying:

$ python3 recursion.pyThis will call each function for a number of examples, and print the result.

For a more thorough test, run the unit tests in test.py, like this:

$ python3 test.py ... ---------------------------------------------------------------------- Ran 3 tests in 0.001s OKThis shows the output when each function works perfectly. If there is any error, you will get error messages, like this:

$ python3 test.py .. ====================================================================== FAIL: test_threes (__main__.TestThrees) (i=2) ---------------------------------------------------------------------- Traceback (most recent call last): File "test.py", line 18, in test_threes self.assertEqual(recursion.number_of_threes(ns[i]), ans[i], ns[i]) AssertionError: 0 != 1 : 3 ====================================================================== FAIL: test_threes (__main__.TestThrees) (i=5) ---------------------------------------------------------------------- Traceback (most recent call last): File "test.py", line 18, in test_threes self.assertEqual(recursion.number_of_threes(ns[i]), ans[i], ns[i]) AssertionError: 3 != 2 : 123454321 ---------------------------------------------------------------------- Ran 3 tests in 0.001s FAILED (failures=2)In this example, the function number_of_threes failed for two of the test cases.

We now describe the three functions you need to implement.

This function determines how often the digit '3' appears in the decimal representation of 'n'.

Your implementation must be recursive, and you are not allowed to use any string methods.

Hint: Look at how we printed numbers in any base.

Here are a few examples:

0 contains 0 threes 7 contains 0 threes 3 contains 1 threes 13 contains 1 threes 33333 contains 5 threes 123454321 contains 2 threes 12333983393893 contains 7 threes

This function determines if the string s is a palindrome (and returns True or False). A palindrome is a string that is equal to its reverse.

Here are a few examples:

'abba' is a palindrome? True 'omma' is a palindrome? False 'a' is a palindrome? True '' is a palindrome? True 'ere' is a palindrome? True 'era' is a palindrome? False 'amanaplanacanalpanama' is a palindrome? True

Your function must be recursive. You are not allowed to write a for- or while-loop, or to use any string methods (except slicing to obtain a substring).

Hint: How can you define the palindrome-property recursively?

This function computes the integer binary logarithm of the integer \(n \geq 1\). The integer binary logarithm is the logarithm with base 2, rounded down. Or, in other words, it is the largest integer \(k>0\) such that \(2^k \leq n\). For example:

binLog(7) = 2 binLog(8) = 3 binLog(17) = 4 binLog(1000) = 9 binLog(1024) = 10 binLog(2500) = 11 binLog(1000000) = 19 binLog(1000000000) = 29

Again, your function must be recursive. No loops are allowed. The power operator ** is not allowed. The math module is also not allowed.

You need to upload your file recursion.py to the submission server.

You have to register with your student id the first time you use the server.

When you register, you have to choose an alias. This alias will be used when I post your homework and exam scores.

You must remember your password. There is currently no way to retrieve or change your password. (In the worst case I can delete your registration so you can register again.)