Python递归列表问题

Question

1.我遇到了这段代码：Python递归和列表

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)

递归搜索可以从第一个元素开始进行吗，例如search(lst[0:],key)？为什么要单独处理第一个元素？

2.为什么这是一种递归算法？

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

- Echo

---

因为这是一个对于编程中的递归新手来说非常好的问题，所以我点了赞。 - Ozgur Vatansever

您不必在点赞时发表评论。 - danidee

这并不是递归，而是称为循环或者圆形对象——一个包含对自身引用的对象。换句话说，你的列表包含对自身的引用，这就是它变成循环的原因。 - GIZ

我敢挑战你调用 search(range(0,1002),1001)。 - kpie

Answer 1

关于第一个问题：

如果您将递归开始为search(lst [0：]， key)，那么您将进入无限递归。请注意，为了使递归停止，您需要每次比之前拥有更小的列表，并且使用search(lst [1：]， key)是这种情况。

另外，关于为什么要单独处理第一个元素，请注意您需要逐个元素与key进行比较，而该元素是lst [0]。

因此，在此递归中，您将问题分为两个部分：（1）检查列表中是否有某个元素等于您的键（该元素始终是当前列表的第一个元素），以及（2）在其余列表中进行递归调用。

关于第二个问题：

这不是递归：

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

这些行的作用是创建一个列表，其中第4个元素是同一个列表：

>>> selfref_list == selfref_list[3] 
True

但这与函数中的递归无关。

- Daniel

---

除了最后一部分selfref_list.append(selfref_list)，我同意你的答案；OP模糊地询问了循环对象。 - GIZ

我认为你需要更广泛地了解语言中递归主题。该概念的联结确实提供了不必完全讨论这个问题的机会，但我宁愿让人们真正思考这个问题。同时参考这个链接：https://zh.wikipedia.org/wiki/递归数据类型 - kpie

Answer 2

为什么要单独处理第一个元素： 因为你的递归方法的每个实例都会完成一部分工作，函数必须检查数组中的一个元素。当你对只有一个元素的列表调用函数时，第一个元素或lst [0]将是唯一剩下的元素，那么为什么不在列表不为空时每次都检查它呢？

这为什么是递归？

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

从最字面上讲，这不是递归。相反，数据类型是递归的，这意味着一个对象可以在同一对象类型的实例中包含自己。或者更正式的数学术语，语法树中的节点类型允许向另一个类似类型的节点输出边缘...

递归语法

递归数据类型

- kpie

Answer 3

对于第一个问题，在第一行中，def search(lst, key)。也就是说，每次调用函数时，它将使用整个lst，这与lst[0:]相同。现在，你之所以有

是因为……

    else: # recursive case: advance to next element in list
        return search(lst[1:], key)

这是定义在遍历完当前第一个元素后发生的操作。基本上，它表示：“在检查完第一个元素之后，继续检查其余元素，从下一个元素开始。”

- jtitusj