In this lab, you will design, implement, and test two recursive algorithms. The
ID: 3596324 • Letter: I
Question
In this lab, you will design, implement, and test two recursive algorithms. The primary goal is to practice
devising a recursive solution to a problem, and then implementing that solution in code. Recall the general
steps to devising a recursive solution:
1.
Identify the subproblems:
What smaller (yet structurally identical) subproblems will be used to solve the
original problem?
2.
Identify how answers are composed:
Once the solutions to the subproblems are in hand, how can they
be combined to get an answer to the original problem?
3.
Identify the base cases:
What are the smallest problems that must be solved directly, without recursion?
4.
Verify termination:
Ensure your solution will not cause infinite recursion.
Write the following two methods inside of a class
Lab5
:
/**
* Reverses the order of the objects in an array using
* recursion
*/
static <T> void reverse(T[] a)
/**
* Replaces each instance of character `before` with
* character `after` within `str`, and returns the
* resulting string (using recursion)
*/
static String replace(String str, char before, char after)
Be sure to test that these methods work as expected! You are provided with class
lab5.Testers
that calls each of the above methods on a few instances, but you should convince yourself that they work in all
scenarios.
Lab5.Testers
Explanation / Answer
Testers.java
import java.util.Arrays;
public class Testers {
public static void main(String[] atsnehdaou) {
// Test reverse() for an integer array
Integer[] intArray = new Integer[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Lab5.reverse(intArray);
System.out.println(Arrays.toString(intArray));
// Test reverse() for a double array
Double[] doubleArray = new Double[] {1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0};
Lab5.reverse(doubleArray);
System.out.println(Arrays.toString(doubleArray));
// Test several replacements on a sample string
String name = "bill garrison";
name = Lab5.replace(name, 'g', 'b');
name = Lab5.replace(name, 'r', 'l');
name = Lab5.replace(name, 'b', 'j');
System.out.println(name);
}
}
Lab5.java
public class Lab5 {
static <T> void reverse(T[] a) {
reverseArray(a, 0, a.length-1);
}
static <T> void reverseArray(T[] x, int i, int j) {
if (i < j) {
T tmp = x[i];
x[i] = x[j];
x[j] = tmp;
reverseArray(x, ++i, --j);
}
}
static String replace(String str, char before, char after) {
if(str.length() <= 0) {
return "";
} else {
if(str.charAt(0) == before) {
return after + replace(str.substring(1,str.length()), before, after);
} else {
return str.charAt(0) + replace(str.substring(1,str.length()), before, after);
}
}
}
}
Output:
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[4.0, 3.5, 3.0, 2.5, 2.0, 1.5, 1.0]
jill jallison
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.