遞歸函數返回值的難度

Question

因此，我正在編寫一個遞歸函數來確定二進制搜索算法列表中的整數的成員資格，並且一旦函數完成遞歸，我無法返回/打印值。說實話，我很難在遞歸的時候回想起來。每當我運行程序時，它都會無限地輸出一半的錯誤信息。我的問題似乎是，如果項目失敗遞歸測試，它不知道何時停止失敗，它只是不斷打印失敗的條件/錯誤消息。

程序一旦完成運行就打印出條件是必須的，所以如果我說is_member（list_of_numbers，83），它將在列表中打印「真」。

這是我工作了幾個小時後的代碼。

def is_member(set, number): 
    if len(set) == 0: 
     print(False) 
    else: 
     midpoint = len(set) // 2 
     #print(midpoint) 
     if set[midpoint] == number: 
      print(True) 
     else: 
      if number < set[midpoint]: 
       if is_member(set[:midpoint], number) == True: 
        print(True) 
      elif number > set[midpoint]: 
       if is_member(set[:midpoint+1:], number) == True: 
        print(True) 
      else: 
       print(False) 


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,] 

is_member(testlist, 3) 
is_member(testlist, 19) 

Answer 1

您當前的遞歸程序不運行，因爲以下條件 -

if is_member(set[:midpoint+1:], number) == True: 

即使midpoint爲0，這將調用is_member()與set片爲 - set[:1:] - 這將是來自set列表的第一個元素。因此，這將繼續下去。條件應該是 -

if is_member(set[midpoint+1:], number) == True: 

因此，您要檢查midpoint的右側。

鑑於此，要將您的程序轉換爲返回結果，您應該返回結果而不是print。示例 -

def is_member(set, number): 
    if len(set) == 0: 
     return False 
    midpoint = len(set) // 2 
    if set[midpoint] == number: 
     return True 
    if number < set[midpoint]: 
     return is_member(set[:midpoint], number) 
    elif number > set[midpoint]: 
     return is_member(set[midpoint+1:], number) 
    return False 

演示 -

>>> def is_member(set, number): 
...  if len(set) == 0: 
...   return False 
...  midpoint = len(set) // 2 
...  if set[midpoint] == number: 
...   return True 
...  if number < set[midpoint]: 
...   return is_member(set[:midpoint], number) 
...  elif number > set[midpoint]: 
...   return is_member(set[midpoint+1:], number) 
...  return False 
... 
>>> testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,] 
>>> 
>>> is_member(testlist, 3) 
False 
>>> is_member(testlist, 19) 
True 
>>> is_member(testlist, 100) 
False 
>>> is_member(testlist, 42) 
True