Programming project 1

In this project you write three short recursive functions: number_of_threes(n), palindrome(s), and bin_log(n) (their precise function is described below).

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

This 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

OK

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

number_of_threes(n)

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

palindrome(s)

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?

bin_log(n)

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.

Submitting the project

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