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