Recursion help!

[johni12]

Hi, I am a newbie here and a python newbie as well :) I am having trouble implementing a program in which you must use only recursive functions and no built-in python functions other than the len function in order to determine if there are duplicates of an item in a given list. The function returns True if there is and False if there isn't. The base condition would be if there is nothing in the list (hence the use of the len function). What I am having trouble with here, is how do you take an item and compare it to the other items in the list to see if they are equal, and if not, discard that item and continue this type of searching? Using only recursive functions? Or is there something else I must do to check for duplicates?

I suppose the general question here would be for example:

Given a list L that is [1,2,3,4,5,1,6], how could I use recursive functions to check if the first index of the list (in this case, 1) is equal to any other indexed item in this list? And if not, discard the first index and make the next index the first index (index 0)? If this is not possible, what is a workaround that provides the result im looking for?

[Mathhax0r]

Being as general as possible, you could pass a list to a function, and if there's a new item not in that list, it's appended to it. If it's already in the list, then you can return true for repeats or w/e.

def doesListHaveRepeats(baseList, whereAt=0, tempList=[]):
    if whereAt == len(baseList): #if you reach the end of the line without a repeat
        return false
    if baseList[whereAt] in tempList: #if you find a repeat
        return true
    else: #if you encounter a distinct value
        tempList.append(baseList[whereAt])
        return doesListHaveRepeats(baseList, whereAt+1, tempList)

[johni12]

thanks for your reply, but I forgot to clarify that I'm restricted to a single parameter (which is the list) and that is part of what makes this so difficult in recursively determining if there is a duplicate in the list. I'm also not allowed to use any built-in functions other than the len function to check the base condition.

My first effort at this program looks like this:

def find_dupe(L):
if len(L)==1:
return False
if L[0]==L[1]:
return True
else:
return(find_dupe([L[0]]+L[2:]))

the obvious flaw here is that the way this function is written it only checks if there are duplicates of the first indexed item in the list. My question would be how do I check for all the other indexed items with all these restrictions applied (i.e. no built-in functions other than len, must use recursive calling, etc)? I have a feeling you need two recursive calls but im not quite sure how to do it. Any help is truly appreciated! Thank you!

[Gribouillis]

You could use

def find_dupe(L):
    if len(L) == 0:
        return False
    elif L[0] in L[1:]:
        return True
    else:
        return find_dupe(L[1:])

[johni12]

That was extremely helpful! I had totally forgotten about the if x in L statement. Thank you very much!!! You rock!