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.
Why does it need to be recursive? And why is it running
restante = busca(lista[1:], alvo)
before checking theprimeiro = lista[0]
with the first if?– Guilherme Nascimento