python recursive list questions

Question

1.I came across this code: Python Recursion and list

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)

Can the recursive search start from the first element as search(lst[0:],key)? Why is the first element treated separately?

2.Why is this a recursion?

selfref_list = [1, 2, 3]
selfref_list.append(selfref_list) 

Answer 1

About the first question:

If you start the recursion as search(lst[0:], key) then you will enter an infinite recursion. Notice that for the recursion to stop you need to have each time a smaller list than before and that is the case with search(lst[1:], key).

Also, as to why the first element is treated separately, notice you need to perform the comparison against key one element at a time, and that element is lst[0].

So in this recursion, you divide the problem in two: (1) you check if some element of the list is equal to your key (this element is always the first element of the current list), and (2) a recursive call in the rest of the list.

About the second question:

This isn't a recursion:

selfref_list = [1, 2, 3]
selfref_list.append(selfref_list)

What those lines do is to create a list where the 4th element is the same list:

>>> selfref_list == selfref_list[3] 
True

But that is not related to recursion in functions.