Python最大遞歸深度達到了錯誤

Question

所以我在這裏得到了一系列搜索字符串中的目標值的函數。
（例如：在$ &（找到R * ,. 02468：<> @BDFHJLNPRTVXZ \ ^`bdfhj，H在索引18）

但是發現當用於功能測試是爲某些字符執行它工作正常，但對於其他一些國家（如d或L）它給我的「最大遞歸深度達到了錯誤」。

也爲前面的字符，如$在$ &（。 02468：<> @BDFHJLNPRTVXZ \ ^`bdfhj，結果是「it ca找不到「*

作爲python的新手，我很難看出這些函數有什麼問題，所以這裏看起來有什麼問題呢？

編輯---------

對不起，我的意思是的混亂似乎是在錯誤的造成最大遞歸深度錯誤，我應該如何開始測試這些功能的功能。

def str_search(data, target, start, end): 

""" 
str_search : String String NatNum NatNum -> NatNum or NoneType 
Description: 
Search for a target value in a sorted data string. 
The search happens between the start and end indices inclusively. 
This starts searching in the middle. If it finds the target, it is done. 
Otherwise it decides whether to search the first half or the second half. 
preconditions: the data string is in ascending alphanumeric order. 
Parameters: 
    data - a string 
    target - the target value to find is a single character string e.g. 'Q' 
    start - the starting index into the data 
    end - the ending index into the data 
Returns: 
    index of target in data, if present; otherwise None. 
""" 

    if start == end: 
     return None 

    mid_index = (start + end) // 2 
    mid_value = data[mid_index] 

# debug statement prints the data. 
#print("Searching for", target, ":", data[start:mid_index], 
# "*" + str(mid_value) + "*", data[mid_index+1:end+1]) 

    if target == mid_value: 
     return mid_index 
    elif target < mid_value: 
     return str_search(data, target, start, mid_index-1) 
    else: 
     return str_search(data, target, mid_index, end) 

def find_target(data, target): 
""" 
find_target : String String -> NatNum or NoneType 
find_target returns the index of target in data or None if not found. 
Parameters: 
    data - a string 
    target - the target value to find 
Returns: 
    The index of the target element in data, if present, or None. 
""" 

    return str_search(data, target, 0, len(data) - 1) 

def makeString(): 
    """ 
    makeString :() -> String 
    makeString returns a String 
    """ 
    data = "" 
    # append characters to make the string 
    for num in range(36, 108, 2): 
     data += chr(num) 
    return data 

def main_search(): 
    """ 
    main_search : Void -> NoneType 
    """ 

    data = makeString() 
    print("Number of elements: ", len(data)) 

    while True: 
     print("\nData: ", data) 
     target = input("Enter a character to find: ") 

     if target == "": 
      break 
     else: 
      index = find_target(data, target) 
      print() 
      if index != None: 
       print(target, "found at index", index) 
      else: 
       print(target, "not found") 
# end while 

Answer 1

，我們在您str_search函數的兩個問題。

1. 下面的代碼在$這是在開始時失敗。您搜索的最終涉及到(start,end)=(0,0)然後start == end會True，返回None

   if start == end: 
       return None 
   

2. 更大的問題是你在當你搜索「d」下面的代碼進入無限遞歸循環。當您搜索d，你的起點和終點將是繼(0,35)，(0,16)，(8,16)，(12,16)，(14,16)，(15,16)，(15,16) .... 無限！

   elif target < mid_value: 
       return str_search(data, target, start, mid_index-1) 
   

我相信兩個以上1和2的修復可以通過處理的情況來完成，其中end - start=1。

刪除下面幾行：

if start == end: 
    return None 

替換：

if (end - start == 1): 
    if target == data[end]: 
     return end 
    elif target == data[start]: 
     return start 
    else: 
     return None 

快速採樣的方法來測試，而無需對您輸入的輸入是：

def testSearch(): 
    data = makeString() 
    for target in data: 
     index = find_target(data, target) 
     print() 
     if index != None: 
      print(target, "found at index", index) 
     else: 
      print(target, "not found") 

testSearch() 

但是，如果你想徹底測試你會更好使用python單元測試並使用斷言。在這裏看到的文檔：https://docs.python.org/2/library/unittest.html

Answer 2

這個工作沒有包含在字符串中的字符錯誤：

if target == mid_value: 
    return mid_index 
elif target == data[mid_index+1]: 
    return mid_index+1 
elif target < mid_value: 
    return str_search(data, target, start, mid_index) 
else: 
    return str_search(data, target, mid_index, end) 

內置Python功能：

data = "something" 
index_of_chr_in_string = data.find("m") 
# or 
print("something".find("t"))