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

你不能像现在这样在运行时修改你的字典。并且在你的代码中，递归调用里没有返回值。

def findword (word, t):
   for i in t:
      if i == word:
         return i

或者如果你还是想使用二分查找的话：

def findword (word, t):
    t.sort()
    return findword_aux(word, t, 0, len(t)-1)

def findword_aux(word, array, first, last):
    midindex = (first + last) / 2 
    midword = array[midindex]
    if last - first == 1:
        return None
    if word == midword:
        return  midword
    elif word > midword:
        return findword_aux (word, array, midindex+1, last)
    elif word < midword:
        return findword_aux (word, array, first, midindex-1)

def run_tests():
    test1()
    test2()

def test1():
    mydic=['apple','banana','peach','pear','melon','lemon','grape','berry'] 
    result = findword('apple', mydic)
    if result == 'apple':
        print 'test1 pass'
    else:
        print 'test1 error'

def test2():
    mydic=['apple','banana','peach','pear','melon','lemon','grape','berry'] 
    result = findword('pinapple', mydic)
    if result == None:
        print 'test2 pass'
    else:
        print 'test2 error'

Answer 2

如果你只是想在一个列表中查找一个单词，你可以这样做——

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 3

二分查找的实现

首先，递归这个东西不太好用。如果可以的话，尽量避免使用它——在很大的搜索范围内，运气不好时可能会出现这种最大递归错误。

我们来换成迭代的方式，看看能做些什么：

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 4

看看这段代码：

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

在你的代码中，会有一个时刻，列表会缩减到只有两个元素，也就是：

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

在这种情况下，看看下面的互动示例：

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的库模块，可以用来做二分查找。