Finding objects with even references tidier

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 evenList (ArrayList tList) {
    ArrayList newList = ListMethods.deepClone(tList);
    int tempStorage = newList.size();

    if (newList.size()  deepClone (ArrayList tList) {
    ArrayList list = new ArrayList();

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

public static void main (String[] args) {
    ArrayList tempList = new ArrayList();
    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 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?

I'm not sure if you're tied to having the method signature public static ArrayList evenList(ArrayList 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 here instead of ArrayList. This may not make sense to you yet - if so, just mentally replace every List with ArrayList.)

public static List evenList(List tList) 
{
    List result = new ArrayList();
    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 tList, List 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 tList, List 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 tList, List 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 tList, List 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 tList, List 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 tList, List result, int index)
{
    if(index  tList, List 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.

StackExchange Code Review Q#22736, answer score: 4