1.1) In this sequence of problems we practice recursion by abandoning our reliance on iteration. We resolve to solve a sequence of problems without using while or for loops. Instead we will think recursively and look at the world through a different lens. Recursion is all about solving a large problem by using the solution to a similar smaller problem. The brilliant thing about recursion is that you can assume you already know how to solve the smaller problem. The goal is to demonstrate how the smaller solution relates to the larger problem at hand. For example, suppose you want to print all binary strings of length 3 and you already know how to print all binary strings of length 2. Here they are: 00 01 10 11 How can we solve the larger problem with a list of strings of length 2? Add a 0 or 1, right? So here is the solution to the larger problem: 00 + 0 = 000 01 + 0 = 010 10 + 0 = 100 11 + 0 = 110 and 00 + 1 = 001 01 + 1 = 011 10 + 1 = 101 11 + 1 = 111 Voila! Not every binary string problem can be solved in terms of a smaller one. At some point we have to declare the smallest problem we are interested in and just solve it. In the case of binary strings, we might agree that the smallest problem we will solve is the 1 digit problem and that the solution is simply 0 and 1. When we write solutions to problems using recursion we will always solve the smallest problem first, so our programs will usually have a similar structure: if this is the smallest problem Just solve it by hand. else Solve the large problem by using a solution to a smaller version of the same problem. Now lets tackle a real problem. Suppose our goal is to produce an ArrayList with Integer objects 1, 2, 3, , n by building a method called makeList(int n). We want to end up with a stand-alone method so we will package the method as a static method. Remember we are refusing to use while and for loops think recursively! Here is the skeleton code: import java.util.*; public class ListMethods { public static ArrayList makeList(int n) { ArrayList tempList = null; if (n <= 0) // The smallest list we can make { } else // All other size lists are created here { } return tempList; } } The smallest problem we will solve is building and returning an ArrayList when n <= 0. In that case we want to return an empty ArrayList. Leave the else block empty for the moment and write the code that will solve this smallest problem. Test it using the test harness listed below: import java.util.ArrayList; public class ListMethodsRunner { public static void main(String[] args) { ArrayList tempList = ListMethods.makeList(0); if (tempList.size() == 0) { System.out.println("The list is empty"); } else { for (Integer i : tempList) { System.out.println(i); } } } } 1.2) We left the else block empty in the last problem. Lets fill it in now. This is where we need to show how we can solve the large problem (building an ArrayList with 1, 2, 3, , n) by using a smaller version of the same problem. What is the next smallest problem? Yes, building an ArrayList with 1, 2, 3, , n - 1 . How can we do that? Heres the brilliant part: We can solve that problem by calling makeList(n 1) the very same method we are trying to write! Thats what makes the recursion happen. Whenever a method calls itself, the method is recursive. By calling the same method again, each instance of a problem is solved using the solution to a smaller instance. Logically, this process has to stop somewhere. In the case of our ArrayList problem, it stops when we call makeList(0). This is the problem we solved by hand in Lab 1.1. Whenever we call makeList(n - 1) we receive an ArrayList with 1, 2, 3, , n - 1. How can we use that to produce an ArrayList with 1, 2, 3, , n? Add that code to the else block and complete the makeList method. Test your code with the test harness by changing the argument that is passed to makeList. Can you make a list with 100 items? 1.3) Lets add another static method to class ListMethods with this header: public static ArrayList reverseList(ArrayList list) This method is passed an ArrayList and returns another ArrayList that contains the same collection of objects in reverse order. There is a version of reverse in the Collections class that would reverse our list for us, but for practice we will write our own recursive algorithm to do this. In designing this method we will insist that the original list that is passed into the method, and the elements it contains, are left unchanged by the method. Because our ArrayList is passed by reference, any changes we make to its elements are reflected in the passed list. Our reverseList algorithm will invoke a remove operation on the list, altering it, so we need to make a copy or a clone of the original list. Although there is a clone method that is inherited by ArrayList, it is a shallow clone and doesnt make copies of the elements of the ArrayList. It simply copies references to the original elements. To solve this problem, we create a method called deepClone that returns a new ArrayList that contains references to the copies of the original elements. Here is the code: public static ArrayList deepClone(ArrayList tList) { ArrayList list = new ArrayList(); for (Integer i : tList) { list.add(new Integer(i)); } return list; } By adding a call to deepClone at the beginning of the reverseList method, we create a copy of the original ArrayList. We work with this list inside the method instead of the original list. We use the same logic pattern as in 1.1. First determine the smallest problem we might need to solve. What is it? Sometimes there is more than one smallest problem that we need to solve by hand. In the case of the reverse method, the smallest problem could be an empty list or a list with one Integer. In both of these cases we can simply return the list unchanged no need to reverse the list. How do we test for these cases? Take the code below and fill in the block to be executed when the condition is true. Leave the other block empty we will handle that next. Modify reverseList so that it makes and reverses an empty list and a list with one element. public static ArrayList reverseList(ArrayList tList) { ArrayList list = ListMethods.deepClone(tList); if (// The list is empty or has one element) { // Return the list as is no need to reverse! } else { // Use the solution to a smaller version of the problem // to solve the general problem } return list; } 1.4) Now we will write the recursive part of the program in 1.3. In solving the problem of reversing a list with n integers, the obvious smaller problem to use is reversing a list with n - 1 integers. Somehow we need to remove an element of the ArrayList. We can use remove(0) to remove the first element. (Another choice would be to remove the last element.) Lets think about how the solution to the smaller problem can help us solve the larger one. Suppose we have the list {1, 2, 3, 4, 5}. Removing the first element leaves us holding 1 and the smaller list {2, 3, 4, 5}. Because we are writing recursively, we can use our own reverseList method on the smaller list to produce the list {5, 4, 3, 2}. Adding the 1 back to this reversed list produces {5, 4, 3, 2, 1} and we are done. Use this idea to write the block to be executed when the condition is false in the reverseList method. Then modify your ListMethodsRunner program to build a list with 100 items and reverse it. 1.5) Now build an even method in the ListMethods class with the following header: public static ArrayList even(ArrayList list) The method returns an ArrayList consisting of the elements of the list argument that are stored at the even indexes 0, 2, 4, . For example, if the original list is [1, 2, 3, 4, 5, 6], method even would return [1, 3, 5] the elements at the even indexes, not the even numbers in the list. What is the smallest list that we might process? Hint: It isnt a list with one element. Using logic similar to the previous programs, complete the method by coding the two blocks in the if/ else sequence. Be sure your even method leaves the list passed to it unchanged. Lets make a plan for our program by examining how the process could work for the list { 1, 2, 3, 4, 5, 6, 7 }. 1) Remove and save the first element at index 0. We are left holding 1 and { 2, 3, 4, 5, 6, 7 }. 2) Remove and discard the new element at the index 0, which is now 2. We are still holding 1 and { 3, 4, 5, 6, 7 }.. 3) Apply even recursively to {3, 4, 5, 6, 7 }. We see that even({3,4,5,6,7}) generates { 3, 5, 7 }. 4) Add the element 2 to the front of the list { 3, 5, 7 }. There is an alternate version of the add method in the ArrayList class that allows you to specify the index of the position where the element will be added. For example list.add(0, x) would add x at the beginning of list. 1.6) Next write an odd method the companion to even with the following header: public static ArrayList odd(ArrayList list) The method returns an ArrayList consisting of the elements of the list that are stored at the odd indexes 1, 3, 5, . Using logic similar to the previous programs, complete the method by coding the two blocks in the if/ else sequence. Be sure your odd method leaves the list passed to it unchanged. 1.7) Build a merge method with the following header: public static ArrayList merge(ArrayList list1, ArrayList list2) The method is passed two sorted lists of type ArrayList and returns a sorted ArrayList containing all the elements of the passed lists. Big Hint: Removing even one element from either list creates a smaller version of the same problem. Also, there is a get method in the ArrayList class that returns a reference to an element but doesnt remove it. Use the following test harness to test your method. Be sure your merge method leaves the lists it is passed unchanged. import java.util.ArrayList; public class ListMethodsRunner { public static void main(String[] args) { ArrayList list1 = new ArrayList(); list1.add(2); list1.add(3); list1.add(5); list1.add(9); list1.add(22); list1.add(38); list1.add(56); ArrayList list2 = new ArrayList(); list2.add(4); list2.add(7); list2.add(8); list2.add(23); list2.add(37); ArrayList tempList = ListMethods.merge(list1, list2); if (tempList.size() == 0) { System.out.println("The list is empty"); } else { for (Integer i : tempList) { System.out.println(i); } } } }