Lab 10.1

In this lab session, 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 ... { // ... is an empty (new) list } else // All other sized (non-empty) lists are created here { // a list [1, 2, ... n] is n added to the end of the list [1, 2, ..., n-1] } return tempList; } } // end class ListMethods

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); } } } // end main method } // end class ListMethodsRunner

Lab 10.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 10.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?

Lab 10.3

Lets add another static method to class ListMethods with this header:

public static ArrayList reverseList(ArrayList tList)

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:

Add this method definition to your class ListMethods:

private 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 Lab 10.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 reverseList 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 the following reverseList method so that it makes and reverses an empty list and a list with one element:

public static ArrayList reverseList(ArrayList tList) { ArrayList list = 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; }

Lab 10.4

Now we will write the recursive part of the program in Lab 10.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 (i.e., the else block) when the condition is false in the reverseList method.

Then modify your ListMethodsRunner program to build a list with 100 items and reverse it.