# CMPT 120 Lab 11

This site applies only to CMPT 120 D1 (Burnaby) in Summer 2011. See the other instructors' pages for other sections.

1. Create a recursive function `gcd(m,n)` that calculates the GCD (greatest common divisor) of the two arguments (which you can assume are integers).

Euclid's Algorithm for calculating the GCD relies on these facts:

gcd(a, 0) = a ,
gcd(a, b) = gcd(b, a%b), for b ≠ 0.

Here are some examples:

>>> print gcd(12, 18)
6
>>> print gcd(18, 31)
1
>>> print gcd(87654, 0)
87654
>>> print gcd(0, 87654)
87654
>>> print gcd(324, 162)
162

Here, the base case will be when `b==0` (return `a`). For the recursive case, return `gcd(b, a%b)`.

2. Create a recursive function `with_commas(n)` that takes a positive integer and returns a string containing its representation with commas every three places. That is, you should return a string with a comma separating the thousands, millions, …. You can assume the argument is a positive integer.
>>> print with_commas(1234567)
1,234,567
>>> print with_commas(123)
123
>>> print with_commas(91273490123741290347)
91,273,490,123,741,290,347

Hint: For the recursive case, use `with_commas(n/1000)` along with `n%1000`.

3. Create a recursive function `evens(lst)` that takes a list and returns the number of even integers in it. Recall that you can check to see if `n` is even with `n%2 == 0`. For example,
>>> print evens([5, 2, 9, 8, 9, 2, 6, 0, 9, 1])
5
>>> print evens([2, 4, 6, 8])
4
>>> print evens([1, 3, 5, 9])
0
>>> print evens([])
0