递归错误Python

Question

我写了一点代码试图在列表中搜索一个单词。 这不是最终版本，基本上它还不能做任何事情。 但是，我不明白代码出了什么问题：

def findword (word, t):
    t.sort()
    midword = t[len(t)/2]
    midindex = len(t)/2
    if word > midword:
        del t[:midindex]
        findword (word, t)
    elif word < midword:
        del t[midindex+1:]
        findword (word, t)
    elif word == midword:
        return t
    else:
        return None

mydic=['apple','banana','peach','pear','melon','lemon','grape','berry']
mydic1 = findword('apple', mydic)

我在搜索apple时遇到了RuntimeError: maximum recursion depth exceeded in cmp错误，当我搜索列表中的其他单词时，它返回空列表。在

请帮我弄清楚是怎么回事。谢谢！在

Answer 1

如果你只是想在列表中搜索一个单词，你可以这样做--

mydic=['apple','banana','peach','pear','melon','lemon','grape','berry']

inputword = 'apple'
if inputword in mydic:
    print('yes it is in the list')
else:
    print('no it is not')

Answer 2

二进制搜索的实现

首先，递归是令人讨厌的。如果可以的话，请避免这种情况——如果不走运的话，它会在非常大的搜索空间中导致这类MaxRecursion错误。在

让我们切换到迭代，看看我们能做些什么：

def binary_search(lst, word):
    new_lst = sorted(lst) # so we only do this once
    return _binary_search(new_lst, word, start=0, end=len(new_lst))

def _binary_search(lst, word, start, end):
    while end - start > 0: # technically this is just while end-start but...
        pivot = (start + end) // 2 # floordiv!
        pivot_element = lst[pivot]
        if word > pivot_element:
            start = pivot + 1
        elif word < pivot_element:
            end = pivot
        else: # word == pivot_element
            return word
    else: return None

>>> my_list = ['apple', 'banana', 'peach', 'pear', 'melon', 'lemon', 'grape', 'berry']
>>> print(binary_search(my_list, "strawberry"))
None
>>> print(binary_search(my_list, "pear"))
"pear"

Answer 3

看看这个代码段：

    elif word < midword:
        del t[midindex+1:]
        findword (word, t)

在您的代码中，您会发现列表只包含两个元素，即：

^{pr2}$

在这种情况下，请查看以下交互式会话：

In [15]: t = ['apple', 'banana']

In [16]: midindex = len(t)/2

In [17]: midindex
Out[17]: 1

In [18]: t[midindex+1:]
Out[18]: []

In [19]: del t[midindex+1:]

In [20]: t
Out[20]: ['apple', 'banana']

请注意，在第19行中，您没有删除任何内容，t保持不变，然后使用相同的列表调用{}，并进入无限递归，直到堆栈空间用完为止。你应该重新设计你的代码来克服这个问题。在

我看到的另一个问题是您只是递归地调用findword，但没有使用返回值。而不是：

    elif word < midword:
        del t[midindex+1:]
        findword (word, t)

您应该：

    elif word < midword:
        del t[midindex+1:]
        return findword (word, t)

其他建议

• {cd2>不要把cd2放在函数里面。排序可能很昂贵，因此您应该只在findword之外执行一次。在
• 正如其他人指出的那样，修改列表是一种不好的做法，相反，重新设计代码而不这样做
• 如果这不是家庭作业或练习，如果你想快速查找，我建议使用set
• Python有一个名为bisect的库模块，它将执行二进制搜索。在