Finding duplicates in a list using recursion?

Question

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;

}

Problem is if you want to find duplicate you need two elements one that you are passing one from the list so you need to add implementation that way — Amit Deshpande
– Amit Deshpande, Commented Oct 24, 2012 at 16:44
When you step through the code in you debugger what do you see goes wrong? — Peter Lawrey
– Peter Lawrey, Commented Oct 24, 2012 at 16:45
Why does it evaluate (and return the result of) duplicate(..) after duplicateHelper(..)? The initial/kickoff method should likely never be called again .. — user166390
– user166390, Commented Oct 24, 2012 at 16:53
@pst duplicateHelper looks for a specific elment t, duplicate looks for the next element in the list — John B
– John B, Commented Oct 24, 2012 at 17:01
can you go through and select an answer for your questions? @TKP — Night
– Night, Commented Jan 23, 2014 at 14:35

Woot4Moo · Accepted Answer · 2012-10-24 16:46:51Z

4

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.

answered Oct 24, 2012 at 16:46

Woot4Moo

24.4k19 gold badges103 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

John B Over a year ago

The problem with this solution is that you change the incoming list and create a new one. This means that you must make a copy of the input list to create one you can safely modify. If memory is not an issue, great.

Woot4Moo Over a year ago

@JohnB It being a homework problem, I am going to let OP figure out the joys of the Iterator object and/or the fun of learning recursive logic.

John B Over a year ago

in the above, removeLastElement needs to be replaced with remove(0) to use Java's List class

Woot4Moo Over a year ago

@JohnB As I said before, this is clearly a homework problem, and it is not my job nor anyone's outside of OP's professor/ TA to give the full working program. Working through my second masters degree now I utilize my professors as often as possible, as being spoon fed doesn't help.

John B Over a year ago

OK, point taken, +1. However, I would suggest that removing the first element is in general more efficient than the last given that the input list could be a linked list.

|

John B · Accepted Answer · 2012-10-24 16:57:38Z

1

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.

answered Oct 24, 2012 at 16:57

John B

33.1k8 gold badges80 silver badges100 bronze badges

2 Comments

user166390 Over a year ago

Logging is not for debugging locally. Debuggers are.

TKP Over a year ago

I've tried passing in sublist to Helper but the problem is when the Helper returned, I don't get the original sublist so I can't look at the next element. Anyway, I got rid of the helper method and re-wrote the code just using the 'duplicate' and it seems to be working now. Thank you.

Collectives™ on Stack Overflow

Finding duplicates in a list using recursion?

2 Answers 2

7 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related