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?

Answer 1

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

Answer 2

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.

Answer 3

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.