Homework: Recursion

< Previous  Next >

---

For this homework assignment, submit a copy of hwkRecursion.cpp. Make changes to your copy according to the directions below.

1. Mystery Method:
Given a recursive method like:

int recursiveFunctionA(int x, int y) {
    if (x == 0 || y == 0)
        return 0;
    else
        return x + recursiveFunctionA(y-1, x);
}

We can trace this recursive method with something like the following. Below are some example calls:

recursiveFunctionA(3, 2) = 3 + recursiveFunctionA(1, 3)
                         = 3 + 1 + recursiveFunctionA(2, 1)
                         = 3 + 1 + 2 + recursiveFunctionA(0, 2)
                         = 3 + 1 + 2 + 0
                         = 6

recursiveFunctionA(1, 4) = 1 + recursiveFunctionA(3, 1)
                         = 1 + 3 + recursiveFunctionA(0, 3)
                         = 1 + 3 + 0
                         = 4

recursiveFunctionA(3, 5) = 3 + recursiveFunctionA(4, 3)
                         = 3 + 4 + recursiveFunctionA(2, 4)
                         = 3 + 4 + 2 + recursiveFunctionA(3, 2)
                         = 3 + 4 + 2 + 6 (from above)
                         = 15

recursiveFunctionA(0, 9) = 0

It multiplies!
Consider the following recursive method below:

int recursiveFunctionB(int a, int b) {
   if (a < b) {
      return 0;
   } else {
      return 1 + recursiveFunctionB(a - b, b);
   }
}

In the comments provided in your hwkRecursion.cpp, answer the following two questions:
1. What is the value returned for each of the following method calls (Show the recursive method calls that are generated)?
   1. recursiveFunctionB( 7, 2);
   2. recursiveFunctionB( 29, 5);
   3. recursiveFunctionB( 5, 7);
2. In the appropriate comment, in just a few words, state what the method is computing (assuming a > 0 and b > 0 for the initial call).


2. Euclid's Algorithm:
   Euclid's Algorithm is a well-known algorithm for computing the greatest common divisor (GCD) of two numbers (see Euclid's Elements Book 7, ca. 300 B.C.). It may be the oldest nontrivial algorithm. Euclid's algorithm is:

   GCD(a, b) = GCD(b, r)

   where we're computing the GCD of a and b and r is the remainder when a is divided by b, then the common divisors of a and b are the same as the common divisors of b and r.
   For example, GCD(36, 20) = GCD(20, 16) = GCD(16, 4) = GCD(4, 0) = 4 meaning that the GCD of 36 and 20 is 4.
   In your hwkRecursion.cpp, provide a recursive implemention for gcd().
   Clearly label the base case with a C++ comment containing at least the phrase "BASE CASE".
   
   Note: If you get stuck, try the following:
   1. Apply the four questions for constructing recursive solutions:
      1. How can you define the problem in terms of a smaller problem of the same type?
      2. How does each recursive call diminish the size of the problem?
      3. What condition(s) can serve as the base case?
      4. As the problem size diminishes, will you reach the base case?
   2. Put a breakpoint in gcd() and use a debugger to walk through your code. Pay careful attention to the call stack.
   
   
3. Make Change: OPTIONAL (worth 0 points!)
   In your hwkRecursion.cpp, write a recursive implemention for makeChange() that counts the number of possible ways to make change for a given amount of money. Let's assume that we are only dealing with coins (and not concern ourselves with paper money). Ultimately, you want a method that takes the following arguments:
   • The number of cents, as an integer
   • An array of integers for each coin (e.g., {1, 5, 10, 25} or {1, 5, 10, 25, 50, 100})
   • Number of coins. For example, if this value is 4, then only use the first four coins: 1, 5, 10, 25.
   For example, makeChange(100, coins, 5) asks how many ways there are to make change for a dollar, using pennies, nickels, dimes and quarters and half-dollars. The answer is 292.
   WARNING: This question is hard. Remember, it is optional. I want you to think about it because it is worth thinking about. Even if you don’t come up with an optimal answer, the process of thinking about it will be valuable.
   
   Note: If you get stuck, try the following:
   1. Solve makeChage( 10, coins, 5)
   2. Solve it by hand!

Your copy needs to compile on ranger using the following command-line:

g++  -std=c++0x  hwkRecursion.cpp

Submission

Submit your cpp file at https://3110.cs.mtsu.edu/. For further instructions, please see the Miscellaneous page.

Rubric:

Points          Item
----------      --------------------------------------------------------------
_____ /  4      1. Mystery Method
_____ /  5      2. Euclid's Algorithm
__0__ /  0	3. Make Change	

_____ /  9      Total
      

Last Modified: