递归搜索布尔返回函数

0 投票

2 回答

4467 浏览

提问于 2025-04-16 07:29

写一个递归函数 search(l, key)，这个函数会返回一个布尔值：如果 key 在列表 l 中，就返回 True；如果不在，就返回 False。请描述一下基本情况（也就是最简单的情况）以及如何将小问题和大问题联系起来。注意，你不能使用 in 操作符或 index() 列表方法。

有没有人能解释一下我在描述部分需要做什么？我对递归一无所知，不知道从哪里开始。这是一个考试复习的实验作业。

这是我得到的代码。

def search(l,key):
    """
    locates key in list l.  if present, returns True; else returns False.
    PRE: l is a list.
    POST: l is unchanged; returns True if key in l; False otherwise.
    """

示例主程序：

l1 = [1, '2', 'x', 5, -2]

print search(l1, 'x')    # should output: "True"

print search(l1, 2)      # should output: "False"

列表操作递归布尔值算法设计搜索算法基本情况递归函数

2 个回答

每次遇到递归的问题，都应该用同样的方法来处理（通常是这样）……首先问自己什么是基本情况，然后在此基础上逐步解决更复杂的情况……

在这个问题中，问问自己，什么时候可以确定列表中没有键……显然，当列表为空时，你可以确定里面没有。

对于更大的列表，你可以先看第一个元素，如果它和键相同，那就直接返回True，但如果不相同，就要对剩下的列表进行所有的检查……

所以，考虑到这些方面，下面就是你的算法。

function locate(lst,key)
    if lst == emptylist then return False
    if lst[0] == key then return True
    else return locate(lst[1..],key) //i use the notation lst[1...] to indicate list starting from 1 index.

回答于 2025-04-16 由 Python大师

分享举报

所有递归的做法大致遵循相同的规则：

要有一个或多个结束条件。
其他情况都是当前情况的一个稍微简单的版本。

举个例子，下面是一种（效率很低）的方法来加两个正数 a 和 b：

如果 b 是零，就返回 a。
否则就加上这两个数 a+1 和 b-1。

大概是这样的：

def addtwo (a, b):
    if b == 0:
        return a
    return addtwo (a+1, b-1)

现在我们来想想你作业中的情况：

如果列表是空的，说明没找到：返回假。
如果列表的第一个元素等于你的关键字，说明找到了：返回真。
否则就去看去掉第一个元素后的列表。

用伪代码表示（这和Python非常相似，但有些地方需要你自己调整）：

def search (list, key):
    if list is empty:
        return false
    if key == first item in list:
        return true
    return search (list with first element removed, key)

回答于 2025-04-16 由 Python大师

分享举报

递归搜索布尔返回函数

2 个回答

撰写回答