Description
Goal
In this lab you will design and implement recursive algorithms. The primary focus in this lab will be algorithms that make a single recursive call.
Resources
-
Chapter 7: Recursion
Java Files
-
RecursiveStringReplace.java
-
TestReplace.java
The goal is to complete a recursive method that will replace all occurrences of a given character with another character.
Compile and run the main method in TestReplace.
Checkpoint: The program will run and get a null pointer exception.
Refer to the string replace recursive design from the pre-lab exercises and complete the method replace() in RecursiveStringReplace.java..
Final Checkpoint: Compile and run TestReplace. All tests should pass.
Post-Lab Follow-Ups
-
Develop a recursive algorithm for computing the product of a sequence of odd values. (Eg. ProdOdd(11) = 1*3*5*7*9*11.) Use that method to develop a recursive algorithm for factorial that splits the problem into a product of even values and a product of odd values.
-
Develop a recursive algorithm that given a and n, computes the sum
S = 1 + a + a2 + … + an
-
Develop a recursive algorithm similar to string replace which works in place on an array of characters.
-
Develop a recursive algorithm for computing the second most significant bit of a number n.
-
Develop a recursive algorithm for computing the result of removing the second most significant bit from a number n.
Adapted from Dr. Hoot’s Lab Manual for Data Structures and Abstractions with Java ™
