Python 递归和列表

Python Recursion and list

提问by gptt916

I am learning about recursion in python and I have this code:

我正在学习 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

Can someone explain to me what the line

有人可以向我解释一下线路是什么

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

does exactly? and what does l[1:] do to the list?

是吗？l[1:] 对列表做了什么？

采纳答案by óscar López

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, headdepending 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:

在函数式编程语言中递归遍历列表的常用方法是使用一个函数访问列表的第一个元素（命名为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

For example, a recursive search function in Python that determines whether an element is or not in a list (a predicate, because it returns Trueor False) would look like this:

例如，Python 中确定元素是否在列表中的递归搜索函数（谓词，因为它返回Trueor 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)

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):

考虑到上面的例子，很容易调整它来解决原始问题 - 如何返回列表中元素的索引（如果找到）或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

回答by thefourtheye

It recursively calls the searchfunction, with the sliced data from l. l[1:]means all the data excluding the elements till the index 1. For example,

它递归地调用该search函数，并使用来自 的切片数据l。l[1:]表示除 index 之前的元素之外的所有数据1。例如，

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 -2and so on. You can read more about this slicing notation in this excellent answer.

当您使用负索引时，最后一个元素用-1，last but one with 表示-2，依此类推。您可以在这个优秀的答案中阅读有关此切片符号的更多信息。

回答by bnjmn

Cool. This is where the recursion happens (as you noted), by calling the function itself given the same keybut a subset of the list l(the first element isn't included).

凉爽的。这是递归发生的地方（如您所指出的），通过调用函数本身给定相同key但列表的一个子集l（不包括第一个元素）。

Basically, it will keep doing this until the keyis found in the list. If so, Truewill 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.

基本上，它会一直这样做，直到key在列表中找到。如果是，True将被退回。否则，整个列表将被遍历，直到列表为空（所有元素都已检查是否与 相等key。此时，算法放弃并返回False。

This will just tell you if the keyis in the list but not what index can be found at.

这只会告诉您 是否key在列表中，但不会告诉您可以在哪个索引处找到。