Python 递归和列表 [英] Python Recursion and list

问题描述

我正在学习 Python 中的递归，我有这个代码:

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)

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

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

推荐答案

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

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

例如，Python 中确定元素是否在列表中的递归搜索函数(谓词，因为它返回 True 或 False)将看起来像这样:

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)

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

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

这篇关于Python 递归和列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！