Python Recursion and list

Question

I am learning about recursion in python and I have this code:

def search(l,key):
    """
    locates key in list l.  if present, returns location as an index; 
    else returns False.
    PRE: l is a list.
    POST: l is unchanged; returns i such that l[i] == key; False otherwise.
    """

    if l:   # checks if list exists
        if l[0] == key:     # base case - first index is key
            return True

        s = search(l[1:], key)      # recursion
        if s is not False:          
            return s

    return False            # returns false if key not found

Can someone explain to me what the line

s = search(l[1:], key)

does exactly? and what does l[1:] do to the list?

[here](http://stackoverflow.com/questions/509211/pythons-slice-notation) — Ricardo Cárdenes, Feb 09 '14 at 14:35
humm, the code doesn't seem to `returns i such that l[i] == key` — laike9m, Feb 09 '14 at 14:39

score 12 · Accepted Answer · edited May 23 '17 at 12:17

12

The usual way to recursively traverse a list in functional programming languages is to use a function that accesses the first element of the list (named car, first, head depending on the language) and another function that accesses the rest of the list (cdr, rest, tail). In Python there isn't a direct equivalent to those functions, but we can to this for the same effect, using slices:

lst[0]  # first element of a list
lst[1:] # rest of the elements in the list, after the first

For example, a recursive search function in Python that determines whether an element is or not in a list (a predicate, because it returns True or False) would look like this:

def search(lst, key):
    if not lst:         # base case: list is empty
        return False
    elif lst[0] == key: # base case: current element is searched element
        return True
    else:               # recursive case: advance to next element in list
        return search(lst[1:], key)

With the above example in mind, it's easy to adapt it to solve the original problem - how to return the index of an element in a list (if found) or False (if not found):

def search(l, key):
    if not l:
        return False
    elif l[0] == key:
        return 0
    else:
        idx = search(l[1:], key)
        return 1+idx if idx is not False else False

edited May 23 '17 at 12:17

Community

1
1

answered Feb 09 '14 at 14:37

Óscar López

232,561
37
312
386

Thank you! I would upvote your answer but I dont have enough rep yet D: – Nick Feb 09 '14 at 14:39
Edit: It works for nested lists, but when I try it with this `search([1, [2, 3], 4, [5, [6 , [], [8, 9]], 10]], 8)` it doesnt return anything? oh and also I modified my code so that it returns true iff s is present in L – Nick Feb 09 '14 at 15:26
To add to the above comment, after some testing it only works for nested lists if the nested list is the last element in the list. I have no idea why this is happening D: – Nick Feb 09 '14 at 15:34
@NickGong the original question doesn't specify that the input list is nested, that leads to a completely different answer. Besides, how would the function be defined? for example, in a list such as `[1, [2, 3], 4]` what would be the index of `2`? is it `1`? is it `0`? you'll have to post it as a different question. – Óscar López Feb 09 '14 at 16:11
Okay, thanks for the input, I will post a different question! – Nick Feb 09 '14 at 17:05

score 3 · Answer 2 · edited May 23 '17 at 12:00

It recursively calls the search function, with the sliced data from l. l[1:] means all the data excluding the elements till the index 1. For example,

data = [1, 2, 3, 4, 5]
print data[1:]            # [2, 3, 4, 5]
print data[2:]            # [3, 4, 5]

You can use the slicing notation to get values between ranges, for example

print data[1:4]           # [2, 3, 4]
print data[2:3]           # [3]

You can also get all the elements till the specific index (excluding the element at the index)

print data[:4]           # [1, 2, 3, 4]
print data[:3]           # [1, 2, 3]

Sometimes you may not know the index of the elements from the end. So, you can use negative indices, like this

print data[-2:]          # [4, 5]
print data[1:-2]         # [2, 3]
print data[:-3]          # [1, 2]

When you use negative indices, the last element is represented with -1, last but one with -2 and so on. You can read more about this slicing notation in this excellent answer.

Oh, i see, so it just keeps using search on the elements and as it goes down it excludes index 0 every time? — Nick, Feb 09 '14 at 14:37

bnjmn · Answer 3 · 2014-02-09T14:46:19.017

Cool. This is where the recursion happens (as you noted), by calling the function itself given the same key but a subset of the list l (the first element isn't included).

Basically, it will keep doing this until the key is found in the list. If so, True will be returned. Otherwise, the entire list will be gone over until the list is empty (all elements have been checked for equality with key. At that point, the algorithm gives up and returns False.

This will just tell you if the key is in the list but not what index can be found at.

score 0 · Answer 4 · answered Jul 11 '22 at 11:34

This is the case when recursion becomes handy (works for nested lists two):

def search_in_list(alist, elem):
    found = False
    for num in alist:
        if num == elem:
            return True
        if isinstance(num, list):
            found = search_in_list(num, elem)
            if found:
                return found
    return found

print(search_in_list([0, [1, [2], 3], [4, [5, [6, [7, [8]]]]]], 5))

Python Recursion and list

4 Answers4

Linked