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

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.