I need some help in writing a lab in Java for computer science. Task #1 Tracing
ID: 3663450 • Letter: I
Question
I need some help in writing a lab in Java for computer science.
Task #1 Tracing recursive methods
1. Copy the file
Recursion.java
(see code listing 15.1) from www.aw.com/cssup-
port or as directed by your instructor.
2. Run the program to confirm that the generated answer is correct. Modify the
factorial method in the following ways:
a) add these lines above the first if statement
int temp;
System.out.println(
"Method call calculating Factorial of: " + n);
b) remove this line in the recursive section at the end of the method
return (factorial(n-1) *n);
c) add these lines in the recursive section
temp = factorial(n-1);
System.out.println(
"Factorial of: " + (n-1) + " is " + temp);
return (temp * n);
3. Rerun the program and note how the recursive calls are built up on the run-time
stack and then the values are calculated in reverse order as the run-time stack
unwinds.
128
Lab Manual to Accompany Starting Out with Java 5: From Control Structures to Objects
Gaddis_516907_Java 4/10/07 2:10 PM Page 128
Task #2 Writing Recursive and Iterative Versions of a
Method
1. Copy the file
Progression.java
(see code listing 15.2) from www.aw.com/cssup-
port or as directed by your instructor.
2. You need to write
class
(static) methods for an iterative and a recursive version
each of the progressions. You will have 4 methods,
geometricRecursive
,
geometricIterative
,
harmonicRecursive
, and
harmonicIterative
. Be sure to match them to the method calls in the
main method.
Chapter 15 Lab Recursion
129
Gaddis_516907_Java 4/10/07 2:10 PM Page 129
Code Listing 15.1 (Recursive.java)
public class Recursion
{
public static void main(String[] args)
{
int n = 7;
//Test out the factorial
System.out.println(n + " factorial equals ");
System.out.println(Recursion.factorial(n));
System.out.println();
}
public static int factorial(int n)
{
int temp;
if (n==0)
{
return 1;
}
else
{
return (factorial(n-1) *n);
}
}
}
130
Lab Manual to Accompany Starting Out with Java 5: From Control Structures to Objects
Gaddis_516907_Java 4/10/07 2:10 PM Page 130
Code Listing 15.2 (Progression.java)
import java.util.Scanner;
public class Progression
{
public static void main(String [] args)
{
Scanner keyboard = new Scanner (System.in);
System.out.println("This program will calculate " +
"the geometric and ");
System.out.println("harmonic progression for the " +
"number you enter.");
System.out.print("Enter an integer that is " +
"greater than or equal to 1: ");
int input = keyboard.nextInt();
int geomAnswer = geometricRecursive (input);
double harmAnswer = harmonicRecursive (input);
System.out.println("Using recursion:");
System.out.println("The geometric progression of " +
input + " is " + geomAnswer);
System.out.println("The harmonic progression of " +
input + " is " + harmAnswer);
geomAnswer = geometricIterative (input);
harmAnswer = harmonicIterative (input);
System.out.println("Using iteration:");
System.out.println("The geometric progression of " +
input + " is " + geomAnswer);
System.out.println("The harmonic progression of " +
input + " is " + harmAnswer);
}
}
Explanation / Answer
Task 1:
a) Modified Recursion class: with modified factorial() method
----------------------------------------------
public class Recursion {
public static void main(String[] args) {
int n = 7;
// Test out the factorial
System.out.println(n + " factorial equals ");
System.out.println(Recursion.factorial(n));
System.out.println();
}
public static int factorial(int n) {
int temp; //added
System.out.println("Method call calculating Factorial of: " + n); //added
if (n == 0) {
return 1;
} else {
//return (factorial(n - 1) * n); //line to be removed as asked. I commented it for your reference.
temp = factorial(n-1); //added
System.out.println("Factorial of: " + (n-1) + " is " + temp); //added
return (temp * n);
}
}
}
-----------------------------------------------------
b) Output:
---------------------------------------
7 factorial equals
Method call calculating Factorial of: 7
Method call calculating Factorial of: 6
Method call calculating Factorial of: 5
Method call calculating Factorial of: 4
Method call calculating Factorial of: 3
Method call calculating Factorial of: 2
Method call calculating Factorial of: 1
Method call calculating Factorial of: 0
Factorial of: 0 is 1
Factorial of: 1 is 1
Factorial of: 2 is 2
Factorial of: 3 is 6
Factorial of: 4 is 24
Factorial of: 5 is 120
Factorial of: 6 is 720
5040
-------------------------------------------
From the output, it is clear that factorials are calculated in reverse of order of their corresponding calls.
Task 2:
Modified Progression class:
-------------------------------------------------
import java.util.Scanner;
public class Progression {
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
System.out.println("This program will calculate " + "the geometric and ");
System.out.println("harmonic progression for the " + "number you enter.");
System.out.print("Enter an integer that is " + "greater than or equal to 1: ");
int input = keyboard.nextInt();
int geomAnswer = geometricRecursive(input);
double harmAnswer = harmonicRecursive(input);
System.out.println("Using recursion:");
System.out.println("The geometric progression of " + input + " is " + geomAnswer);
System.out.println("The harmonic progression of " + input + " is " + harmAnswer);
geomAnswer = geometricIterative(input);
harmAnswer = harmonicIterative(input);
System.out.println("Using iteration:");
System.out.println("The geometric progression of " + input + " is " + geomAnswer);
System.out.println("The harmonic progression of " + input + " is " + harmAnswer);
}
// This function calculates the harmonic progression of a given number till
// the terms equal to the given number.
private static double harmonicIterative(int input) {
// TODO Auto-generated method stub
double sum = 0;
for (int i = 1; i <= input; i++) {
sum += (double) (1.0 / (input + (i - 1) * input));
}
return sum;
}
// This function calculates the geometric progression of a given number till
// the terms equal to the given number.
private static int geometricIterative(int input) {
// TODO Auto-generated method stub
int sum = 0;
for (int i = 1; i <= input; i++) {
sum += Math.pow(input, i);
}
return sum;
}
// This method calculates the harmonic progression of a given number through
// recursion till the terms equal to the given number.
// Here to maintain the value of difference, another method with same name,
// but with different signatures is defined. This method is called
// recursively to return the next term in the progression.
private static double harmonicRecursive(int input) {
// TODO Auto-generated method stub
int diff = input;
int terms = input;
double firstTerm = input;
double sum = 0;
if (terms == 1) {
sum = 1;
} else {
for (int i = 1; i <= terms; i++)
sum += 1.0 / harmonicRecursive(firstTerm, diff, i); // calculates
// sum by
// inverting
// the
// corresponding
// A.P.
// term.
}
return sum;
}
// actually returns the next term of corresponding arithmetic progression
// through recursion
private static double harmonicRecursive(double firstTerm, int diff, int terms) {
// TODO Auto-generated method stub
if (terms == 1)
return firstTerm;
else
return (diff + harmonicRecursive(firstTerm, diff, terms - 1));
}
// This method calculates the geometric progression of a give number through
// recursion till the terms equal to the given number.
// Here to maintain the value of ratio, another method with same name, but
// with different signatures is defined. This method is called
// recursively to return the next term in the progression.
private static int geometricRecursive(int input) {
// TODO Auto-generated method stub
int ratio = input;
int terms = input;
int firstTerm = 1;
int sum = 0;
if (terms == 1) {
sum = 1;
} else {
for (int i = 1; i <= terms; i++)
sum += geometricRecursive(firstTerm, ratio, i);
}
return sum;
}
// returns the next term of geometric progression through recursion.
private static int geometricRecursive(int firstTerm, int ratio, int terms) {
if (terms == 1)
return firstTerm * ratio;
else
return ratio * geometricRecursive(firstTerm, ratio, terms - 1);
}
}
--------------------------------------------------