Implementing Recursive Algorithms

Implementing Recursive Algorithms
In Lab # 5, we refined static methods written in Lab # 2 to compute the GCD of two numbers, the
LCM of two numbers, the factorial of a number and a term of the Fibonacci sequence. Recursion
can seem mind-boggling at first, but it is a very real and important problem-solving technique
that is an alternative to iteration. Some problems can have compact and elegant recursive
solutions. In this lab session, you will rewrite the methods of the AuxiliaryMath class of Lab # 5
as recursive methods and add a recursive square root method.
Recursive Definition of Some Functions
Here are piecewise recursive definitions for the GCD, factorial and Fibonacci algorithms that
were implemented in Lab #2 and Lab # 5. Rewrite each method using the definitions given
below.
Greatest Common Denominator
gcd(a, b) =



N aN , a = 0 and b = 0
|a + b| , a = 0 or b = 0
gcd(b, a mod b) , otherwise
(1)
Factorial
n! =



N aN , n < 0
1 , n = 0
n × (n − 1)! , otherwise
(2)
Fibonacci Number
F(n) =



N aN , n < 1
0 , n = 1
1 , n = 2
F(n − 1) + F(n − 2) , otherwise
(3)
Least Common Multiple
Implement the lCM as a derived method of gCD using this relationship:
lcm(a, b) = (
N aN , a = 0 or b = 0
a×b
gcd(a,b)
, otherwise
(4)
Assignment № 6 Page 1
Square Root
There is an elementary algorithm used to find the square root of a number that takes advantage
of a mathematical principle commonly referred to as the pinching (a.k.a. squeezing or sandwich)
theorem. Setting aside some mathematical formalisms, the theorem simply means that given
any closed continuous interval [a, b], there is a number p such that a ≤ p ≤ b. We can easily
show that such a number,p, exists. a+b
2
, the midpoint between a and b, satisfy the inequality.
How does this relate to our square root algorithm? We know that √
n is between 0 and n. We
would like to keep narrowing, “squeezing", the interval to obtain better and better approximations
of √
n. We can terminate the algorithm when our approximation is within some predetermined
tolerance (?).
For example to find √
100, we first consider the initial interval [0.100]. We then square 50, the
midpoint of the interval. 50×50 100, so we can obtain a better approximation by squeezing
our interval to its lower half, [0, 50]. Next, we consider the midpoint of this interval. 25×25 100,
so again we consider the lower half of the interval, [0, 25]. 12.5×12.5 100, so we narrow the
interval to [0, 12.5], the lower half of the interval. 6.25×6.25 < 100, so, this time, we narrow the
interval to its upper half since √
100 is greater than 6.25 but less than 12.5. We use the interval
[6.25, 12.25]. 9.375×9.375 < 100, so we narrow the interval to its upper half, [9.375, 12.25], etc. If
we continue to halve the interval to one containing the √
n, we will eventually obtain a midpoint
whose square gives us 100. Due to truncation and roundoff errors by computers, we pick a very
small number, so that if the approximation is within that tolerance, we terminate the algorithm
and return the midpoint as the ’best’ approximation of the square root of 100. The smaller the
tolerance, the better the approximation. Our tolerance must be a small positive number. If 0
is used as the tolerance, the algorithm may not terminate due to truncation or roundoff errors.
Formally, here is a recursive definition of the square root algorithm:
rSqrt(n, lo, hi, ε) =



undef ined , n < 0
lo+hi
2
,



n −

lo+hi
2
?2


 < ε
rSqrt
n, lo, lo+hi
2
, ε?
,

lo+hi
2
?2
n
rSqrt
n, lo+hi
2
, hi, ε?
, otherwise
where n, is the number whose square root is to be found, lo and hi are endpoints of the interval,
and ? (epsilon), is the tolerance. In implementing this algorithm, do not use the standard Java
library power method, Math.pow. To obtain a square of a number, multiply the number by itself.
Define two additional methods in the AuxiliaryMath class:
1. public static sqrt(double n), a wrapper method for the recursive method that computes an
approximation of √
n. This method throws an NotANumberException when n is negative.
It calls the recursive square root method defined above with the parameters n, lo = 0,
hi = n and ? = 1E-9.
2. private static recSqrt(double n, double lo, double hi, double epsilon), a method that recursively approximates √
n using the ’squeezing’ theorem described above. It does not report
an exception since that is already done by the wrapper method.
Assignment № 6 Pa
Additional Requirements
Exhaustively, test your program to ensure that it works. Also, test your program with inputs that
will generate an exception. Write header comments for each class using the follow Javadoc
documentation:
/**
* Explain the purpose of this class; what it does <br
* CSC 1350 Lab # 6
* @author YOUR NAME
* @since DATE THE CLASS WAS WRITTEN
* @version 3
*/
For the AuxiliaryMath class, after the @since line, add the following Javadoc:
* @see NotANumberException
For the AuxiliaryMathDemo class, after the @since line, add the following Javadoc:
* @see AuxiliaryMath, NotANumberException
Add Javadoc style documentation for each method in the NotANumberException and AuxiliaryMath classes. Add Javadoc style documentation for the two methods added to the AuxiliaryMath
class. Also, add code to the AuxiliaryMathDemo class that prompts the user for a number and
then calculates its square root using the square root method that you defined in AuxiliaryMath.
See Sample Run 1 for how the prompt and answer should be displayed. Run the Javadoc utility
to make sure that it generates documentation for these classes. Locate your source files, NotANumberException.java, AuxiliaryMath.java and AuxiliaryMathDemo.java, and enclose them in
a zip file, YOURPAWSID_lab06.zip, and submit your lab assignment for grading using the digital
dropbox set up for this purpose. Here are three sample program interactions:
Listing 1: Sample Run 1
1 Enter three integers whose GCD is to be found - 75 90 100
2 Enter two integers whose LCM is to be found - 25 40
3 Enter a non-negative integer n to find n! - 6
4 Enter two positive integers i and j, where i < j - 1 5
5 Enter a number whose square root is to be found - 7
6
7 gcd(75,90,100) = 5
8 lcm(25,40) = 200
9 6! = 720
10 fib(1) + ... + fib(5) = 7
11 sqrt(7.000000) = 2.645751
Assignment № 6 Page 3
Listing 2: Sample Run 2
1 Enter three integers whose GCD is to be found - 0 5 100
2 Enter two integers whose LCM is to be found - 0 20
3 auxiliarymathdemo.NotANumberException: lCM invoked with a 0 argument.
Listing 3: Sample Run 3
1 Enter three integers whose GCD is to be found - 12 60 96
2 Enter two integers whose LCM is to be found - 50 80
3 Enter a non-negative integer n to find n! - 7
4 Enter two positive integers i and j, where i < j - -4 8
5 auxiliarymathdemo.NotANumberException: fibonacci invoked with an argument ←-
that is not positive.
Assignment № 6 Page 4