Trying to make recursive code designed to find objects with even references tidier

Question

As the title says, I'm trying to make my code less horrible looking! For a university practical, I've to use recursive methods to return the even references in a collection of Integer objects stored in an ArrayList. For example, if the input is [1, 2, 3, 4], my method should return [1, 3] (i.e. elements 0 and 2, the even elements).

My code works, but I feel is horrible:

import java.util.*;

public class ListMethods {

public static ArrayList<Integer> evenList (ArrayList<Integer> tList) {
    ArrayList<Integer> newList = ListMethods.deepClone(tList);
    int tempStorage = newList.size();

    if (newList.size() <= 0)
        return newList;
    else 
    {                                                               
        if (newList.size()%2==0)                                    
            tempStorage = newList.remove(newList.size()-2);          
        newList.remove(newList.size()-1);                           
        newList = ListMethods.evenList(newList);                    
        if (tempStorage!=0)
            newList.add(tempStorage);                               
    }                                                               
    return newList;                                                 
}

public static ArrayList<Integer> deepClone (ArrayList<Integer> tList) {
    ArrayList<Integer> list = new ArrayList<Integer>();

    for (Integer i : tList)
        list.add(new Integer(i));
    return list;
}

public static void main (String[] args) {
    ArrayList<Integer> tempList = new ArrayList<Integer>();
    tempList.add(1);
    tempList.add(2);
    tempList.add(3);
    tempList.add(4);
    tempList.add(5);
    tempList.add(6);

    for (Integer i : tempList)
    { System.out.println (i); }

    ArrayList<Integer> evenList = ListMethods.evenList(tempList);
    System.out.println();

    for (Integer i : evenList)
    { System.out.println (i); }
}
}

The cloning section I have to include, at our lecturer's request. The real part I'm looking to tidy up is the if/else inside the evenList method.

Does anybody have any ideas? Kind regards in advance.

Answer 1

I'm not sure if you're tied to having the method signature public static ArrayList<Integer> evenList(ArrayList<Integer> tList) and if you have to use the deepClone method you've got here, but if you aren't tied down to these restrictions, there are cleaner ways of doing this.

Firstly, one of the main points of recursion is using the stack to store state - this doesn't seem to really come through in your example. Let's think about the problem a bit: we want to go over each element in our list, adding that element to another list if the index of that element is even. How would we do this in "normal" code? Well, we'd just loop over the List with a for loop, probably:

(Note: I use List<Integer> here instead of ArrayList<Integer>. This may not make sense to you yet - if so, just mentally replace every List<Integer> with ArrayList<Integer>.)

public static List<Integer> evenList(List<Integer> tList) 
{
    List<Integer> result = new ArrayList<Integer>();
    for(int i = 0; i < tList.size(); ++i) {
        if(i % 2 == 0) {
            result.add(tList.get(i));
        }
    }
    return result;
}

So converting this to recursive code, what state do we store in the function that we can store on the stack instead? Well, both the result and the index, i. So instead of creating a new List that we return, let's pass both of those in as parameters instead:

public static void evenList(List<Integer> tList, List<Integer> result, int index)

So, with this recursive method, how will we know when to stop? Well, exactly like in our for loop: when our index is at tList.size():

public static void evenList(List<Integer> tList, List<Integer> result, int index)
{
    if(index < tList.size()) {
       ...
    }
}

Ok, so what about the logic? Well, it hasn't really changed much - we still want to do the exact same thing, that is, if index is even, add the element at that index to our result list:

public static void evenList(List<Integer> tList, List<Integer> result, int index)
{
    if(index < tList.size()) {
        if(index % 2 == 0) {
            result.add(tList.get(index));
        }
    ...
}

Now, we need a call to the function itself (otherwise it wouldn't be recursive!), but what parameters do we pass through? Well, we always need tList, so that should go through. We want to keep adding to the same result, so that should go through. However, our index needs to change - we want to test the next element - so that should be ++index. So our final function looks like:

public static void evenList(List<Integer> tList, List<Integer> result, int index)
{
    if(index < tList.size()) {
        if(tList.get(index) % 2 == 0) {
            result.add(tList.get(index));
        }
        evenList(tList, result, ++index);
    }
}

I'm not really sure why your professor has you using clone methods here - it's really inefficient. Every single recursive call, you call deepClone on the List you pass in - this is a lot of wasted effort.

In fact, if we were being really clever here, we would see that every second element gets added to our return list, so we can skip one of the if checks:

public static void evenList(List<Integer> tList, List<Integer> result, int index)
{
    if(index < tList.size()) {
        result.add(tList.get(index));
        index += 2;
        evenList(tList, result, index);
    }
}

Of course, this only works properly when the user passes in an even initial value, presumably 0. So let's make sure that happens. Let's make this method private and supply the starting index:

private static void evenList(List<Integer> tList, List<Integer> result, int index)
{
    if(index < tList.size()) {
        result.add(tList.get(index));
        index += 2;
        evenList(tList, result, index);
    }
}

public static void evenList(List<Integer> tList, List<Integer> result)
{
    evenList(tList, result, 0);
}

If you are tied to the original method signature, well, I've typed a lot of stuff for not much good I suppose, although I'd have to question why your professor had made you do it this way.

Answer 2

Well, what we want to do? Add every second element to the new list, starting with the first.
So a simplified description could be:

function evenList(list)
  if list is empty or has only 1 element
    return list
  return new list(first element of list, evenList(all elements from the third to the end))

translate to algorithm in Java:

public static List<Integer> evenList(final List<Integer> list) {
    if (list.size() <= 1)
        return list;

    final List<Integer> newList = new ArrayList<>(Arrays.asList(list.get(0)));
    newList.addAll(evenList(list.subList(2, list.size())));
    return newList;
}

This version has (after compilation) the exact same signature. If it must be the same before compilation, we could do this:

public static ArrayList<Integer> evenList2(final ArrayList<Integer> list) {
    if (list.size() <= 1)
        return list;

    final ArrayList<Integer> newList = new ArrayList<>(Arrays.asList(list.get(0)));
    newList.addAll(evenList2(new ArrayList<>(list.subList(2, list.size()))));
    return newList;
}

I would suggest to use the first version.

---

About your code:

public static ArrayList<Integer> evenList (ArrayList<Integer> tList) {

The name is not that helpful. I would suggest getNewListFromEvenIndices. But ok, you are forced to use this name. You could propose it at least.

---

ArrayList<Integer> newList = ListMethods.deepClone(tList);

Could be:

ArrayList<Integer> newList = new ArrayList<Integer>(tList);

---

int tempStorage = newList.size();

You could name it size or newListSize, this would be a more clear name. (As we see later, this variable is not needed)

---

if (newList.size() <= 0)
    return newList;

Either use your variable or even better, use newList.isEmpty() to make the meaning clear.

---

else     
{  

You do not need to specify an else clause here. Save braces, save intendation.

---

    if (newList.size()%2==0)                                    

Even if it is quite clear, I would suggest in such case to introduce a private method which is called isEven. Because it is not clear for all readers. And if we make it this way, we could also switch to a logical and:

private boolean isEven(int number)
{
    return (number & 1) == 0;
}

---

        tempStorage = newList.remove(newList.size()-2);

This does not make any sense. Before, tempStorage was the size, now it is the value of a list element. This are 2 completely different meanings.
You should not do such things. (And It will obviously fail for the example [0, 0])

---

    newList.remove(newList.size()-1);                           
    newList = ListMethods.evenList(newList);                    
    if (tempStorage!=0)
        newList.add(tempStorage);        

I am not sure about the plan behind this. You want to remove the last element, which should have an uneven index here? After this, you want to add the element at the probably even index? You can not do it in this way then, you have to introduce for example some boolean variable which could be named elementFromSecondLastIndexMustBeAdded and add it only if it is true.
And you do not need to save it temporally, you could just access the original list tList.

---

So if we try to keep your way, we could have something like:

public static ArrayList<Integer> evenList(final ArrayList<Integer> tList) {
    // plan: if list is empty, return. If not look at the last indices.
    // Remove the uneven one, add the even one to a new list.
    // Do this in recursion until we do not have any last indices.
    if (tList.isEmpty())
        return newList;
    ArrayList<Integer> newList = new ArrayList<>(tList);
    boolean elementFromSecondLastIndexMustBeAdded = false;
    if (isEven(newList.size())) { // if size is even, the last is uneven, the second last is even
        elementFromSecondLastIndexMustBeAdded = true;
        newList.remove(newList.size() - 2);
    }
    newList.remove(newList.size() - 1);
    newList = ListMethods.evenList(newList);
    if (elementFromSecondLastIndexMustBeAdded)
        newList.add(tList.get(tList.size() - 2));
    return newList;
}

private static boolean isEven(final int number) {
    return (number & 1) == 0;
}

The method is still rather complex and needs some comments, because your recursion goes over the end, which is a bit unusual if both cases are possible.

---

And just because I do not like such question were seomone is forced to make bad solutions:

public static List<Integer> evenList(final List<Integer> list) {
    final List<Integer> newList = new ArrayList<>();
    for (int i = 0; i < list.size(); i += 2)
        newList.add(list.get(i));
    return newList;
}

This is valid according to the method signature.

---

If you really have to add a deepClone method, add one with an empty body. Hint: If we are exact, this is not a clone method. For int, yes. For Integer, no.

Answer 3

1. The original list is not changing. List has a subList(int fromIndex, int toIndex) method. So there is no need to clone the items in the list, or to write your own "deepClone" method.

2. Recursion is a technique most often associated with functional programming, so there are a few things I'd do to make this example more "functional."

2.a. Replace tempList with an immutable list, call it "inList" for input-list:

final List<Integer> inList;
{
    List<Integer> tempList = new ArrayList<Integer>();
    tempList.add(1);
    tempList.add(2);
    tempList.add(3);
    tempList.add(4);
    tempList.add(5);
    tempList.add(6);
    inList = Collections.unmodifiableList(tempList);
}

2.b. @Yuushi had a lot of really good suggestions, but for this specific example, I'm not excited about his stylistic choice of making evenList() return void. We can make it a function, that evaluates to something, and for that, we want to keep closer to your original signature, just a slightly more generic version with Lists replacing ArrayLists (this accommodates the Unmodifiable list and is generally better style):

List<Integer> evenList (List<Integer> tList)

OK, now here's the recipe for a recursive function like this one that takes the place of a loop in imperative programming:

How to write a recursive function.

1. determine simplest possible input and output types for your method signature.

2. (Optional) define invalid input conditions (throw exceptions for invalid input)

3. define termination conditions (how to know from the input when you are done)

4. define what to return when termination condition is reached

5. (Optional) Sometimes you may have a special return for the pre-termination condition?

6. define what to return in all other cases

Like a loop, you want to define your exit condition up front, but unlike a loop, a tail-recursive function "unrolls" from the outside-in, like winding up a top and letting it go. So the exit condition of the loop will also be the creation condition for your first return value.

List<Integer> evenList (List<Integer> tList) {
  if (evenList.length() < 1) {
      return new ArrayList<Integer>();
  }
  // TODO: You have to handle the case where evenList.length() == 1
  // Since this is homework, I can't just give you the whole answer.
  // Without that case, there is a bug.

Replacing mutable variables with final ones is more functional. Using the ?: operator instead of if/else for evaluation - this is more functional as well.

  final int keeperIdx = (evenList.length() % 2) == 0 ?
                        evenList.length() - 2 :
                        evenList.length() - 1;

  // Here is the recursive call, passing a slice of the original list.
  // parameters to subList are first zero-based index inclusive, and last
  // index exclusive.
  // prepend the result of this recursive eventList() call to your output.
  return evenList(tList.subList(0, keeperIdx))
             .add(0, tList.get(keeperIdx));
}

I did not test this code, and I left out one necessary condition (clearly marked with a TODO). I hope that it shows enough of the concepts for you to get it working. I'm assuming that your teacher wants to teach you some functional programming concepts, so I tried to lean as far in that direction as Java will comfortably go. I hope it helps!

P.S. There is a small chance that I got confused and am returning your result in reverse order. See if you can mentally figure out whether that's the case, and what three characters to delete if it is.