Intro to Recursion
A simple example from stackoverflow with OOD:
class Calculation
{
int fact(int n)
{
int result;
if(n==1)
return 1;
result = fact(n-1) * n;
return result;
}
}
public class Factorial
{
public static void main(String args[])
{
Calculation obj_one = new Calculation();
int a = obj_one.fact(4);
System.out.println("The factorial of the number is : " + a);
}
}
Assignments:
1. Use the same visual representation as the one above for 4!
2. 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.
3. 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 4.
Rational
//********************************************************************
// Rational.java Author: Lewis/Loftus/Cocking
//
// Represents one rational number with a numerator and denominator.
//********************************************************************
public class Rational
{
private int numerator, denominator;
//-----------------------------------------------------------------
// Sets up the rational number by ensuring a nonzero denominator
// and making only the numerator signed.
//-----------------------------------------------------------------
public Rational (int numer, int denom)
{
if (denom == 0)
denom = 1;
// Make the numerator "store" the sign
if (denom < 0)
{
numer = numer * -1;
denom = denom * -1;
}
numerator = numer;
denominator = denom;
reduce();
}
//-----------------------------------------------------------------
// Returns the numerator of this rational number.
//-----------------------------------------------------------------
public int getNumerator ()
{
return numerator;
}
//-----------------------------------------------------------------
// Returns the denominator of this rational number.
//-----------------------------------------------------------------
public int getDenominator ()
{
return denominator;
}
//-----------------------------------------------------------------
// Returns the reciprocal of this rational number.
//-----------------------------------------------------------------
public Rational reciprocal ()
{
return new Rational (denominator, numerator);
}
//-----------------------------------------------------------------
// Adds this rational number to the one passed as a parameter.
// A common denominator is found by multiplying the individual
// denominators.
//-----------------------------------------------------------------
public Rational add (Rational op2)
{
int commonDenominator = denominator * op2.getDenominator();
int numerator1 = numerator * op2.getDenominator();
int numerator2 = op2.getNumerator() * denominator;
int sum = numerator1 + numerator2;
return new Rational (sum, commonDenominator);
}
//-----------------------------------------------------------------
// Subtracts the rational number passed as a parameter from this
// rational number.
//-----------------------------------------------------------------
public Rational subtract (Rational op2)
{
int commonDenominator = denominator * op2.getDenominator();
int numerator1 = numerator * op2.getDenominator();
int numerator2 = op2.getNumerator() * denominator;
int difference = numerator1 - numerator2;
return new Rational (difference, commonDenominator);
}
//-----------------------------------------------------------------
// Multiplies this rational number by the one passed as a
// parameter.
//-----------------------------------------------------------------
public Rational multiply (Rational op2)
{
int numer = numerator * op2.getNumerator();
int denom = denominator * op2.getDenominator();
return new Rational (numer, denom);
}
//-----------------------------------------------------------------
// Divides this rational number by the one passed as a parameter
// by multiplying by the reciprocal of the second rational.
//-----------------------------------------------------------------
public Rational divide (Rational op2)
{
return multiply (op2.reciprocal());
}
//-----------------------------------------------------------------
// Determines if this rational number is equal to the one passed
// as a parameter. Assumes they are both reduced.
//-----------------------------------------------------------------
public boolean equals (Rational op2)
{
return ( numerator == op2.getNumerator() &&
denominator == op2.getDenominator() );
}
//-----------------------------------------------------------------
// Returns this rational number as a string.
//-----------------------------------------------------------------
public String toString ()
{
String result;
if (numerator == 0)
result = "0";
else
if (denominator == 1)
result = numerator + "";
else
result = numerator + "/" + denominator;
return result;
}
//-----------------------------------------------------------------
// Reduces this rational number by dividing both the numerator
// and the denominator by their greatest common divisor.
//-----------------------------------------------------------------
private void reduce ()
{
if (numerator != 0)
{
int common = gcd (Math.abs(numerator), denominator);
numerator = numerator / common;
denominator = denominator / common;
}
}
//-----------------------------------------------------------------
// Computes and returns the greatest common divisor of the two
// positive parameters. Uses Euclid's algorithm.
//-----------------------------------------------------------------
private int gcd (int num1, int num2)
{
while (num1 != num2)
if (num1 > num2)
num1 = num1 - num2;
else
num2 = num2 - num1;
return num1;
}
}
[collapse]
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
4. Design and implement a recursive program, Pascal_YI.java to determine and print the Nth line of Pascal’s Triangle, as shown below. Each interior value is the sum of the two values above it. Hint: use an array to store the values on each line.
