python - 递归错误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

看看这段代码:

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

在您的代码中，您会发现列表被缩减为只有两个元素，即:

t == ['apple', 'banana']

在这种情况下，请查看以下交互式 session :

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 并进入无限递归，直到用完堆栈空间。您应该重新设计代码以解决此问题。

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

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

你应该这样做:

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

其他建议

• 不要将t.sort() 放在findword 函数中。排序可能代价高昂，因此您应该只在 findword 之外执行一次。
• 正如其他人指出的那样，修改列表是一种不好的做法，而是重新设计您的代码而不是这样做
• 如果这不是家庭作业或练习，如果你想快速查找，我建议使用set
• Python 有一个名为 bisect 的库模块，它可以进行二分查找。