有人可以解釋爲什麼這解決了我的遞歸錯誤？

Question

我是在Python遞歸執行二進制搜索（我知道這是不好的），並得到了與下面的代碼最大遞歸錯誤：

def bs_h(items,key,lower,upper): 
    if lower == upper: 
     return None 
    mid = (lower + upper) // 2 
    if key < items[mid]: 
     return bs_h(items,key, lower, mid) 
    else: 
     return bs_h(items,key,mid,upper) 

def bs(items,key): 
    return bs_h(items,key, 0, len(items)-1) 

然後我改變了我的參數和基本情況，像這樣：

def bs_h(items,key,lower,upper): 
    if lower + 1 == upper: 
     return None 
    mid = (lower + upper) // 2 
    if key < items[mid]: 
     return bs_h(items,key, lower, mid) 
    else: 
     return bs_h(items,key,mid,upper) 

def bs(items,key): 
    return bs_h(items,key, -1, len(items)) 

這解決了錯誤，但我不知道爲什麼。有人可以解釋嗎？

Answer 1

無論何時使用遞歸（有時非常有用），您需要注意極端的有關結束條件。

1. 它終止嗎？
2. 如果有，它會有多深？

在你的代碼的運行過程中的某個時刻，你可能有這樣一個電話：

bs_h(items, key, 10, 11) 

然後導致：

mid = (lower + upper) // 2 
    = (10 + 11) // 2 
    = 10 
if key < items[10]: 
    return bs_h(items, key, 10, 10) 
else: 
    return bs_h(items, key, 10, 11) 

注意最後一句話 - 這是相同的作爲入場通話。如果程序在此時結束，它將始終以遞歸方式運行。

總是檢查你如何擺脫遞歸，順便說一句，檢查你的「新的改進版本」。

Answer 2

什麼修復你的代碼是這樣的變化：

if lower + 1 == upper: 
    return None 

的變化bs是無關緊要的（至少對於這個目的，我真的反對它）。

的原因可以從下面的實驗中觀察到：

>>> (0+0)//2 
0 

>>> (0+1)//2 
0 

因此，中點不會改變一次的時間間隔爲< = 1，因此它遵循你應該儘早停止，否則你將繼續循環等待中點改變，永遠不會發生。

Answer 3

將一個print(lower, upper, mid)聲明您mid = (lower + upper) // 2語句後您的第一個bs_h例子，注意以下事項：

>>> bs(list(range(10)), 5) 
0 9 4 
4 9 6 
4 6 5 
5 6 5 
5 6 5 
... # repeats until max recursion depth. 

由於兩個(n+n)//2和(n+n+1)//2都是一樣的，你到一個地步，你連續調用bs_h相同的lower和upper參數。 您應該調整後續調用以消除邊界條件（已經被選中）。你還需要返回類似索引的東西。以下你想要的遞歸模式匹配，並返回正確的索引：

def bs_h(items,key,lower,upper): 
    if lower > upper: 
     return None 
    mid = (lower + upper) // 2 
    if key < items[mid]: 
     return bs_h(items,key, lower, mid-1) 
    elif key > items[mid]: 
     return bs_h(items,key,mid+1,upper) 
    else: 
     return mid #Found! return index 

而且測試：

>>> for i in range(10): 
    print(bs(list(range(10)), i)) 

0 
1 
2 
3 
4 
5 
6 
7 
8 
9 

>>> print(bs(list(range(10)), 4.5)) 
None 

>>> print(bs(list(range(10)), 100000)) 
None 

Answer 4

格倫Rogeres是正確的。 但是，爲了確保事情都沒有錯過，

• 首先，它的二進制搜索 - 這意味着要找到一個排序列表值。
• 你可以檢查後（一旦 元素被發現在你的情況，mid變量！）返回元素的索引
• 如果關鍵是<或>比項目[MID]你可以忽略中期在你的下一個遞歸搜索元素（MID-1或中期+ 1）

也就是說，

def bs_h(items,key,lower,upper): 
    if lower>upper:return None 
    mid = (lower + upper)// 2 
    if key < items[mid]: 
     return bs_h(items,key, lower, mid-1) 
    elif key > items[mid]: 
     return bs_h(items,key, mid+1, upper) 
    else:return mid 

def bs(items,key): 
    return bs_h(sorted(items),key, 0, len(items)-1)