In this lab, you will work through two divide & conquer recursive methods. The primary goal is to prac ce devising a recursive solu on to a problem, and then implemen ng that solu on in code. Recall the general steps to devising a recursive solu on:
1. Iden fy the subproblems: What smaller (yet structurally iden cal) subproblems will be used to solve the original problem? In divide & conquer, these must be frac onal in size, rela ve to the original problem.
2. Iden fy how answers are composed: Once the solu ons to the subproblems are in hand, how can they be combined to get an answer to the original problem?
3. Iden fy the base cases: What are the smallest problems that must be solved directly,
without recursion?
4. Verify termina on: Ensure your solu on will not cause infinite recursion.
Exercise
• er the TA’s lesson, write the following two methods inside of a class cs445.lab9.Lab9 . Note that you completed similar (nonD&C) methods in Lab 6.
/**
• Reverses the order of the objects in an array, using
• divide and conquer recursion
*/
static void reverse(T[] a)
/**
• Replaces each instance of character before with
• character after within str, and returns the resulting
• string (using divide and conquer 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 cs445.lab9.Testers that calls each of the above on a few instances, but you should convince yourself that they work in all scenarios
