CSC 311 Winter 2002

Assignment 2

Due: Monday, January 21st

This assignment asks to write a set of three recursive functions, each computing a mathematical function.

1. The first function you are to write should be called harmonic. It takes a single integer parameter n  with the precondition that n is greater than 0 and computes the n^th Harmonic number, which is the sum of the reciprocals of the integers from 1 to n.  For example, the fourth Harmonic number is 1/1 + 1/2 + 1/3 + 1/4, which is approximately 2.08333.  The function must be recursive.  

2. The second function should be called choose.  It takes two integer parameters n and k, with the precondition that they are both non-negative and that k is less than or equal to n.  The function should compute "n choose k", which is the number of ways to choose k items from n items.  For example, "5 choose 2" is 10 because there are 10 ways to choose 2 items from a set of 5 items.  

There are several ways to compute the choose function.  You will use the following recursive definition:

• 0 choose k = 0, for k > 0
• n choose 0 = 1, for n > 0
• n choose k = [(n-1) choose k] + [(n-1) choose k-1], for n > 0 and k > 0

3. The third function should be called gcd.  It takes two integer parameters a and b, with the preconditions that they are both non-negative and that a is not less than b.  It should compute the greatest common divisor of a and b, that is, the largest integer that divides both a and b evenly.  For example, the gcd of 15 and 10 is 5.  

Compute the function using the following recursive definition:

• gcd(a, 0) = a, for any a
• gcd(a, b) = gcd(b, a mod b), where a mod b is the remainder when b is divided into a

What to submit

Place all three functions into a file called recursive.cpp.  E-mail this file to me as an attachment and with the subject: CSC 311, your last name, recursive.