CODEWITHSUNDEEP
pythonlistsearchrecursion
Matthew Hanson
Matthew Hanson

Reputation: 331

Python recursive list search function

I have to write a recursive function to search a list for a specific value. The function is supposed to find whether or not the number is in the list and if it is it will return the list index of that value.

For example:

search([1,2,3,4,5],3)

should return:

2

as 3 appears in list index 2.

Right now I have:

def search(myList, number):
    if myList[0] == number:
        return myList[0]
    return search(myList[1:], number)

and it keeps returning 3 for the same function call I had earlier. Any help will be greatly appreciated.

Upvotes: 1

Views: 14409

Answers (2)

Anshul Goyal
Anshul Goyal

Reputation: 76987

There are 2 mistakes in your current code, you return the number iteself, instead of its index, and you don't really pass the incremented index back. So, do this instead:

>>> def search(myList, number):
...     if myList[0] == number:
...         return 0
...     return 1 + search(myList[1:], number)
... 
>>> search([1,2,3,4,5],3)
2

Now that works if we have the number within the list, but if not, we will get an index error.

>>> search([1,2,3,4,5],6)
IndexError: list index out of range

So, we should wrap the function in a try-except block

def search(myList, number):
    def search_recursive(lst, num):
        if lst[0] == num:
            return 0
        return 1 + search_recursive(lst[1:], num)
    try: return search_recursive(myList, number)
    except IndexError: return -1

And now, it will work

>>> search([1,2,3,4,5],6)
-1
>>> search([1,2,3,4,5],5)
4

But the above should be used only when you want to do this recursively, and note that when you do list[1:], you perform list slicing which creates a new list everytime.

So, if doing this without recursion is allowed, use the builtin list.index method:

>>> def search(my_list, number):
...     try: return my_list.index(number)
...     except ValueError: return -1
... 
>>> search([1,2,3,4,5],5)
4
>>> search([1,2,3,4,5],6)
-1

Upvotes: 5

Hackaholic
Hackaholic

Reputation: 19753

You can also use index built-in method:

>>> def search(my_list, val):
...     try:
...         return my_list.index(val)
...     except valueError:
...         return "not found"
...
>>> search([1,2,3,4,5],3)
2

Upvotes: 2

Related Questions