CODEWITHSUNDEEP
javalistrecursion
TKP
TKP

Reputation: 453

Finding duplicates in a list using recursion?

I'm suppose to find if there is duplicates in a list and return true or false using recursion only (no loops). So if ArrayList of char is used, [a,b,c,d,e] should return false. [a,a,b,c,d] or [a,b,b,c,c,d] should return true. I've tried and tested different ways and it worked for some cases but not all. I changed my code around and this is what I have now. (Has problem at the last if statement) Can anyone give me some hints? Thanks.

    public static <T> boolean duplicate(List<T> list) throws NullPointerException {
        return duplicateHelper(list, list.get(0));
}

public static <T> boolean duplicateHelper(List<T> list, T t){
    if (list == null)
        throw new NullPointerException();
    if(list.isEmpty())
        return false;
    if(list.size() > 1){
        if(t.equals(list.get(1)))
            return true;        
    }
    if(list.size() == 1)
        return false;
    if(!duplicateHelper(list.subList(1,list.size()), t)){
        return  duplicate(list.subList(1,list.size()));
    }
    return false;

}

Upvotes: 1

Views: 4808

Answers (2)

John B
John B

Reputation: 32959

Recursion is assisted by pre and post conditions. Things that are always true at start and finish. What I see is that when you first enter duplicateHelper, elements t is at position 0 of the passed list. However, when you recurse into duplicateHelper the sublist that is passed no longer contains t at index 0 but instead contains the element that was previously compared.

Consider passing a sublist from duplicate to duplicateHelper and moving the comparison check to a not empty else. Add logging statements to figure out where the code goes wrong.

Upvotes: 1

Woot4Moo
Woot4Moo

Reputation: 24316

I would recommend doing something like this: 

function recurse(myList, seenList)  
{  
    currentElement =     myList.removeLastElement();
    if(seenList.contains(currentElement)    
     {
        return false;  
      }
    seenList.add(currentElement);   


    return recurse(myList,seenList);
}

While I realize this is homework, I tried to make it as straight forward as possible without giving the complete solution.

Upvotes: 4

Related Questions