CS 1713 Section 1 Spring 2011, Homework 6

Recursion

Do the following problems from the book:

EX 11.5: Modify the method that calculates the sum of the integers between 1 and N shown in this chapter. Have the new version match the following recursive definition: The sum of 1 to N is the sum of 1 to (N/2) plus the sum of (N/2+1) to N. Trace your solution using an N of 7.
The original method in Chapter 11 looks like this:
```
public int sum (int num) {
	int result;
	if (num == 1)
		result = 1;
	else
		result = num + sum (num-1);
	return result;
}
```
EX 11.7: Write a recursive method to reverse a String. The method should accept a String parameter and return the string with the characters in reverse order. Explain why you would not normally use recursion to solve this problem.
PP 11.2: Design and implement a program that implements Euclid's algorithm for finding the greatest common divisor of two positive integers. The greatest common divisor is the largest integer that divides both values without producing a remainder. An iterative version of this method was part of the RationalNumber class presented in Chapter 6. In a class called DivisorCalc, define a static method called gcd that accepts two integers: num1 and num2. Create a driver to test your implementation. The recursive algorithm is defined as follows:
- gcd (num1, num2) is num2 if num2 ≤ num1 and num2 divides num1
- gcd (num1, num2) is gcd (num2, num1) if num1 < num2
- gcd (num1, num2) is gcd (num2, num1 % num2) otherwise

What To Turn In

Turn in each Java file as a separate attachment to a single email message to our teaching assistant. For the first problem that asks you to trace the solution, include a separate text file as an additional attachment that shows the value of the parameter N for each recursive invocation of the method, indented with a number of spaces equal to the depth of the recursion (i.e., the number of spaces before the value of N should be the number of returns that would have to be executed to get back to the main driver program).

Each piece of code you write should contain no loops because for this assignment we are replacing iteration with recursion. If you find yourself writing do/while, while, or for, you are on the wrong track.

This program is due at 11:59pm, Monday, April 11, 2011.

Late assignments will not be accepted. If you're not done with some part before it's due, turn in what you have for partial credit. Don't cheat.