1.1 In this sequence of problems we practice recursion by abandoning our relianc

Question

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

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:

Now let’s 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:

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 code shown below:

---------------------------------------------------------------------------------------------------------------

1.2) We left the else block empty in the last problem. Let’s 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 ArrayListn - 1. How can we do that? Here’s the brilliant part: We can solve that problem by calling makeList(n – 1) - the very same method we are trying to write! That’s 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).

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) Let’s add another static method to class ListMethods with this header:

public static ArrayList<Integer> reverseList(ArrayList<Integer> list)

This method is passed an ArrayList<Integer> and returns another ArrayList<Integer> 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<Integer> 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 doesn’t 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:

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.

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. In the else clause, you can reverse the list recursively:

1. Remove the first element

2. Recursively reverse the rest of the list

3. Add the first element to the end of the reversed list

Modify reverseList so that it makes and reverses a list with any number of elements (including none).

Explanation / Answer

import java.util.*; public class ListMethods { public static ArrayList makeList(int n) { ArrayList tempList = null; if (n

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.