Today

More on Recursion

Ex 4: 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.
Hint: modNSum(1, N/2) + modNSum(N/2 +1,N)
Write a driver to test your program.

Trace your solution using an N of 5.

// This method returns the sum of 1 to num
public int sum (int num) 
{
   int result; 
   if (num == 1)
       result = 1;
   else
       result = num + sum (num-1); 
   return result;
}

Ex 5:
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 7.
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