RecursionError: максимальная глубина рекурсии превышена в сравнении для выполнения бинарного поиска - PullRequest
Новая
       15

RecursionError: максимальная глубина рекурсии превышена в сравнении для выполнения бинарного поиска

0 голосов
/ 17 марта 2019

Это словарная программа для использования python. Но я нашел ошибку с таким. Я хочу знать причину, что я видел .. Если вы знаете об этом, пожалуйста, спросите меня.

Вот ошибка, которую я получаю: 

$ read datafile.txt
$ size
176050
$ find Yesterday
Traceback (most recent call last):
  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 55, in <module>
    word_index = binarysearch(words,word,0,len(words)-1)
  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 25, in binarysearch
    return binarysearch(data, target,middle+1, end)
  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 23, in binarysearch
    return binarysearch(data,target,begin,middle-1)
  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 23, in binarysearch
    return binarysearch(data,target,begin,middle-1)
  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 23, in binarysearch
    return binarysearch(data,target,begin,middle-1)
  [Previous line repeated 994 more times]
  File "C:/Users/LG/PycharmProjects/alg1/lesson1.py", line 13, in binarysearch
    if begin > end:
RecursionError: maximum recursion depth exceeded in comparison

Process finished with exit code 1

Вот мой код: 

def datafile(file):
    f = open(file,'rt',encoding='UTF8')
    while True:
        line = f.readline()
        if not line:
            break
        if line == '\n':
            continue
        lines.append(line.split('\n')[0])
    return lines

def binarysearch(data,target,begin,end):
    if begin > end:
        if data[end]:  #"end" index's front data exist  
            return end
        else:
            return -1
    else:
        middle = int(begin+end/2)
        if data[middle] == target:
            return middle
        elif data[middle] > target:
            return binarysearch(data,target,begin,middle-1)
        else:
            return binarysearch(data, target,middle+1, end)


if __name__=="__main__":

    lines = []  # all list
    words = []  # list that all words is changed to lower
    pos = []  # word's pos list

    while True:
        commend = input("$ ")

        if len(commend.split()) == 2:
            second = commend.split()[1]

        first = commend.split()[0]

        if first == "size":
            print(len(lines))

        if first == "read":
            lines = datafile(second)

            for i in lines:
                words.append(i.split()[0].lower())
                pos.append(i.split()[1])

        if first == "find":
            # receive index, and print word that fitted to condition
            word = second.lower()
            word_index = binarysearch(words,word,0,len(words)-1)

            if words[word_index] in words: # if return value is middle variable
                print(lines[word_index])
                cnt = 1
                while words[word_index] == words[word_index+1]:
                    print(lines[word_index])
                    cnt = cnt + 1
                print("Found",cnt,"items.")

            else:  #if return value is the same with "end" variable                
                print("Not found")
                print(lines[word_index].split()[0],lines[word_index].split()[1])
                print("- - -")
                print(lines[word_index+1].split()[0], lines[word_index+1].split()[1])

            #print(lines[word_index])
            #print(words[word_index])

        if first == "exit":
            break

1 Ответ

1 голос
/ 17 марта 2019

В вашем алгоритме двоичного поиска есть ошибка: 

middle = int(begin+end/2)

Поскольку деление имеет приоритет перед сложением, это не будет вычислять среднюю позицию. Это может привести к тому, что middle станет больше end, а если data[middle] > target, то следующий интервал будет больше при следующем рекурсивном вызове. Это может привести к бесконечной рекурсии.

Исправить на: 

middle = int((begin+end)/2)

Или просто: 

middle = (begin+end)//2
...