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 中没有直接等同于这些函数，但我们可以使用 slices 来达到同样的效果。 :

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