Recursive algorithm to check if an element belongs to a list

Question

I have to do a recursive function that takes a list and a target element, and returns True, whether the element is in the list; and False, otherwise.

EXAMPLES:

busca([1,2,3], 2) --> retorna True
busca([], 49) --> retorna False

I can’t use the guy’s remote x in lista python.

Code:

def busca(lista, alvo):
    primeiro = lista[0]
    restante = busca(lista[1:], alvo)

    if (primeiro == alvo):
        return True
    elif restante == alvo:
        return True
    else:
        return False

Answer 1

^{I understand it’s an exercise and they require the algorithm to be recursive, but for cases like this, recursion is not the best solution, because it’s an unnecessary complication. The operator in native language is the most correct and idiomatic option, and if it did not exist, a simple loop would be a better option than recursion.}

---

The basic idea of the search is: check if the first element of the list is the same as the one being searched for. If it is, return True. Otherwise, search the rest of the list (from the second element). In code, it looks like this:

def busca (lista, alvo):
    if not lista: # lista vazia, elemento não existe
        return False
    if lista[0] == alvo: # primeiro elemento da lista igual ao alvo
        return True
    # faz a busca no restante da lista (do segundo elemento em diante)
    return busca(lista[1:], alvo)

I do an additional check at the beginning, to see if the list is empty: if not lista: checks if the list is empty. This works because an empty list is considered a false value. Anyway, if the list is empty, it means that there is no element, and therefore the target will not be there. So in this case I can already return False.

Then I check if the first element of the list (lista[0]) is equal to the target. If it is, I can already return True and don’t even need to check the rest of the list. This is one of the errors in your code: you have to check the first element before to search in the rest of the list, but you were only doing this check after (another error is that you missed checking the case of the empty list, and while trying to do lista[0] in an empty list, gives error).

If the first element is not what I’m looking for, I’ll search the rest of the list. In case, lista[1:] creates another list, containing from the second element onwards (or an empty list, if the list has only one element).

Testing:

print(busca ([1, 2, 3], 3)) # True
print(busca ([1, 2, 3], 4)) # False
print(busca ([], 2)) # False

---

Just so you understand, let’s see how the algorithm behaves to busca ([1, 2, 3], 3):

• the list is not empty, does not enter the if not lista
• the first element (1) is not equal to the target (3), then don’t get into the if lista[0] == alvo
• makes the search in lista[1:], which corresponds to [2, 3].
  • now the lista is no longer [1, 2, 3], and yes [2, 3]
  • the list is not empty, does not enter the if not lista
  • the first element (2) is not equal to the target (3), then don’t get into the if lista[0] == alvo
  • makes the search in lista[1:], which corresponds to [3]
    • now the lista is no longer [1, 2, 3], and yes [3]
    • the list is not empty, does not enter the if not lista
    • the first element (3) is equal to the target (3), then return True

And in case of busca ([1, 2, 3], 4):

• the list is not empty, does not enter the if not lista
• the first element (1) is not equal to the target (4), then don’t get into the if lista[0] == alvo
• makes the search in lista[1:], which corresponds to [2, 3].
  • now the lista is no longer [1, 2, 3], and yes [2, 3]
  • the list is not empty, does not enter the if not lista
  • the first element (2) is not equal to the target (4), then don’t get into the if lista[0] == alvo
  • makes the search in lista[1:], which corresponds to [3]
    • now the lista is no longer [1, 2, 3], and yes [3]
    • the list is not empty, does not enter the if not lista
    • the first element (3) is not equal to the target (4), then don’t get into the if lista[0] == alvo
    • makes the search in lista[1:], which corresponds to []
      • now the lista is no longer [1, 2, 3], and yes []
      • the list is empty, returns False

As you can see, several sub-lists are created (for an initial list with N elements, up to N sub-lists can be created in the worst case - when the element does not exist in the list), which is quite inefficient. A loop simple would be a better solution (if there were no in, of course, which is the simplest and most idiomatic form).

It is also worth remembering that, if the list is too large, all this amount of recursive calls can cause a pile overflow (example). In the case of the above algorithm, some languages can optimize the tail recursion and this problem would not occur, but the Python does not do this optimization (thanks to @jsbueno for confirm this in the comments).

---

Just to explain in more detail why your algorithm doesn’t work:

def busca(lista, alvo):
    primeiro = lista[0]
    restante = busca(lista[1:], alvo)

    if (primeiro == alvo):
        return True
    elif restante == alvo:
        return True
    else:
        return False

Assuming the call is busca([1, 2], 2):

• takes the first element (1)
• makes the search in lista[1:], which corresponds to [2]
  • takes the first element (2)
  • makes the search in lista[1:], which corresponds to []
    • takes the first element (lista[0]), but since the list is empty, it gives IndexError

IE, missed to check if the list is empty, and also check if the first is equal to the target, before to try searching in the rest of the list.

Answer 2

Make a comparison if the list size is greater than 0 and then another comparison to check if the list size is greater than 1.

Another thing is the comparison that results in error restante == alvo, remainder returns a boolean, so I put to check if returns True the remainder.

Solution:

def busca (lista, alvo):
    if (len (lista) > 0):
        primeiro = lista[0]
    else:
        return False
    if (len (lista) > 1):
        restante = busca (lista[1:], alvo)
    else:
        restante = False
    if (primeiro == alvo):
        return True
    elif restante == True:
        return True
    else:
        return False

print(busca ([1, 1,2], 2))