CODEWITHSUNDEEP
pythonrecursion
HoopStart
HoopStart

Reputation: 39

Use recursion to determine if a given element is in a list

This should be super simple, I know, but I think there's something inherent about recursion I am not getting. The below code works but is not recursive. I think I just cannot wrap my head around using recursion when it doesn't seem necessary. Anyway. I've been knocking my head against a wall with this for a while, any help appreciated!

def contains_element(my_list, elem):
    i=0
    while i< len(my_list):
        if my_list[i]==elem:
            return True
        i+=1
        
    return False
    
 
print(contains_element([1, 2, 3, 4, 5], 5))

Upvotes: 0

Views: 1097

Answers (2)

sahasrara62
sahasrara62

Reputation: 11238

using recursion

  1. check if array is empty or not. if yes then return False
  2. take one element from array, (used pop here, to take last element ) and check whether it is equal to the required element or not.
  3. if equal then return True
  4. using property of or operator, (commutative and associative ie (a or b == b or a ) and (TRUE or True, true or false, false or true, all are true ), just false or false is false ), implement recursion. where we are checking each element is equal to search value and if yes the return True otherwise call funciton again and check for other elments

it contains(arr, ele) = ((arr[-1] == ele) or (arr[-2] == ele) or (arr[-3] == ele) ... (arr[0] == ele))

def contains(arr, ele):
    if not arr:
            return False
    val = arr.pop()
    return val == ele or contains(arr, ele)

arr = list(range(1, 11))
print(contains(arr, 3)) # True
print(contains(arr, 32)) # False

Upvotes: 0

Bill Lynch
Bill Lynch

Reputation: 81996

I usually think of recursion the same way I think of induction. To do this, I need to determine two things:

The Base Case

The simplest base case here, would be if my_list == []. If it was the empty list. Clearly in that case, we would return False.

The Iterative Case

Secondly, we want to determine some way to have my_list approach the base case. Here, a simple thing to do would be to pop off the front or back of the list, test that, and then recurse on the remainder of the list.

What does this look like?

def contains_element(my_list, elem):
  if my_list == []:
    return False
  elif my_list[0] == elem:
    return True
  else:
    return contains_element(my_list[1:])

Upvotes: 3

Related Questions