Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Python Recursion and list

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?

like image 796
Nick Avatar asked Feb 09 '14 14:02

Nick


People also ask

What is a recursion in Python?

Python also accepts function recursion, which means a defined function can call itself. Recursion is a common mathematical and programming concept. It means that a function calls itself. This has the benefit of meaning that you can loop through data to reach a result.

What are recursive lists?

A recursive definition: A list is either. • empty, written [], or • constructed, written x:xs, with head x (an element), and tail xs (a list). Cons (:) is special: any list can be written using : and [], in only one way. Notice: the definition of lists is SELF-REFERENTIAL.

What are the advantages of recursion in Python?

Python Recursion Function AdvantagesA recursive code has a cleaner-looking code. Recursion makes it easier to code, as it breaks a task into smaller ones. It is easier to generate a sequence using recursion than by using nested iteration.


3 Answers

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
like image 176
Óscar López Avatar answered Oct 19 '22 23:10

Óscar López


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.

like image 3
thefourtheye Avatar answered Oct 19 '22 22:10

thefourtheye


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.

like image 1
bnjmn Avatar answered Oct 19 '22 21:10

bnjmn