1. All of your programs must have good internal documentation. You must document every class, every constructor, and every function.

Problem 1: [5 marks] Compute greatest common divisor using recursion

(filename: TestRecusiveGCD.cpp)

The gcd(m, n) can be defined recursively as follows:

If m % n is 0, gcd (m, n) is n.

Otherwise, gcd(m, n) is gcd(n, m % n).

Write a recursive function to find the GCD. Write a test program that prompts the user to enter two integers and displays their GCD.

Problem 2: [10 marks] Binary to decimal (filename: BinaryToDecimal.cpp)

Write a recursive function that parses a binary number as string into a decimal integer. The function header is:

int binaryToDecimal(const string& binaryString)

Write a test program that prompts the users to enter a binary string and displays its decimal equivalent.

Problem 3: [15 marks] String permutation (filename: StringPermutation.cpp)

Write a recursive function to print all the permutations of a string. For example, for a string abc, the permutation is

abc

acb

bac

bca

cab

cba

(Hint: Define the following two functions. The second is a helper function.)

void displayPermutation(const string& s)

void displayPermutation(const string& s1, const string& s2)

The first function simply invokes displayPermutation(“”, s). The second function uses a loop to move a character from s2 to s1 and recursively invoke it with a new s1 and s2. The base case is that s2 is empty and prints s1 to the console.

For example

s1:

s2: abc

s1: a b c

s2: bc ac ab

s1: ab ac ba bc ca cb

s2: c b c a b a

s1: abc acb bac bca cab cba

s2:

Write a test program that prompts the user to enter a string and displays all its permutations.