Python递归和列表

Question

我正在学习python中的递归,我有这个代码:

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

有人可以向我解释一下这行

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

确切地说？以及l [1:]对列表做了什么？

Answer 1

通常的方法来递归遍历函数式编程语言列表是使用访问列表(命名的第一个元素的功能car,first,head取决于语言)和访问列表的其余部分(另一种功能cdr,rest,tail).在Python中没有直接等效于这些函数,但我们可以使用切片来达到相同的效果:

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

例如,Python中的递归搜索函数确定列表中是否存在元素(谓词,因为它返回True或者False)将如下所示:

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)

考虑到上面的例子,它很容易适应它来解决原始问题 - 如何返回列表中的元素索引(如果找到)或False(如果没有找到):

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