python之运行递归二进制搜索算法时出现段错误_编程设计

所以我第一次尝试递归，在 Python 3 中编写了一个简单的二进制搜索算法。运行我的程序后我得到了这个错误:调用 Python 对象时超出了最大递归深度我做了一些研究，它说要添加这一行:sys.setrecursionlimit(40000)

我做到了。当我输入一个不在我的列表中的数字时，我得到了这个 Segmentation Fault 错误。我读了这个post根据我在 Python 中收集到的信息，深度递归会耗尽内存吗？

我无法想象 Python 不支持深度递归？无论如何，这是我的代码:

import sys 
 
arr = [5, 17, 23, 33, 39, 44, 58, 62, 70, 74, 82, 99] 
end = len(arr) 
sys.setrecursionlimit(40000) 
 
def binarySearch(arr, start, end,  x): 
 
   #print("This is end: {}".format(end)) 
    mid = int((end + start)/2) 
    #print("This is start {}".format(start)) 
    #print("This is end {}".format(end)) 
    #print("This is mid {}".format(mid)) 
 
    if x == arr[mid]: 
        return x 
    elif (x < arr[mid]): 
        start = 0 
        end = mid - 1 
        return binarySearch(arr, start, end, x) 
    else: # if x > arr[mid] 
        start = mid + 1 
        end = end 
        return binarySearch(arr, start, end,  x) 
 
 
position = binarySearch(arr, 0, 12, 55) 
print(position)

请您参考如下方法:

您的代码中有几个错误:

您没有基本案例。在进行递归之前，您应该检查是否 start > end。
start = 0 确实应该是 start = start，或者根本不添加它。

修复这些错误，稍微清理一下你的代码，这行得通 -

def binarySearch(arr, start, end, x): 
    if start <= end: 
        mid = (end + start) // 2 
 
        if x == arr[mid]: 
            return mid 
        elif x < arr[mid]: 
            end = mid - 1            
        else: 
            start = mid + 1 
 
        return binarySearch(arr, start, end, x) 
 
    return -1

binarySearch(arr, 0, len(arr), 55) 
-1 
 
binarySearch(arr, 0, len(arr), 58) 
6

另请注意，对于 O(logN) 算法，您永远不需要 40,000 的最大递归深度。如果您遇到“超出最大递归深度”错误，您应该首先重新评估您的算法。