為什么我這個遞歸的binary search 會recursion depth exceeded

hmchzb19

1. #binary search recursive
   
2. def binary_search_rec(seq,key,low=0,high=None):
   
3.     low=0
   
4.     high=len(seq)-1
   
5.     mid=(high+low)//2
   
6.     if not seq or low > high:
   
7.         return False
   
8.     if seq[mid]==key:
   
9.         return mid
   
10.     if key < seq[mid]:
    
11.         return binary_search_rec(seq,key,low,mid)
    
12.     else:
    
13.         return binary_search_rec(seq,key,mid,high)
    
14. 
    
15. #binary search iterative
    
16. def binary_search_iter(seq,key):
    
17.     hi,lo=len(seq)-1,0
    
18.     while lo < hi:
    
19.         mid=(hi+lo)//2
    
20.         if key==seq[mid]:
    
21.             return mid
    
22.         elif key < seq[mid]:
    
23.             hi=mid
    
24.         else:
    
25.             lo=mid+1
    
26.     return False
    
27. 
    
28. import bisect
    
29. def test_binary_search2():
    
30.     seq=[1,2,5,6,7,10,12,12,14,15]
    
31.     key=6
    
32.     print(binary_search_iter(seq,key))
    
33.     print(binary_search_rec(seq,key))
    

復制代碼

rubyish

回復 1# hmchzb19

1. #!/usr/bin/ruby -w
   
2. 
   
3. def bisere seq, key, low, high
   
4.     # if reset low = 0. high = size - 1
   
5.     # no way: low > high
   
6.    
   
7.     return nil if low > high
   
8.     mid = ( high + low ) / 2
   
9.     if seq[mid] == key
   
10.         mid
    
11.     elsif key < seq[mid]
    
12.         bisere seq, key, low, mid - 1   # here: mid - 1
    
13.     else
    
14.         bisere seq, key, mid + 1, high  # here: mid + 1
    
15.     end
    
16. end
    
17. 
    
18. seq = [ 1, 2, 5, 6, 7, 10, 12, 12, 14, 15 ]
    
19. key = 6
    
20. ret = bisere seq, key, 0, seq.size - 1  # here: low, high
    
21. puts ret
    
22. __END__
    

復制代碼

bskay

回復 1# hmchzb19

python的特性就是不能很多次的遞歸,估計原因可能是因為python在后臺維護了很多資源,比如調(diào)用棧需要很多的屬性,每個屬性可能又有很多屬性....
就是最基本的屬性,對應到C/C++上面是要占用不少內(nèi)存等資源的....
實際用的資源就很多了

另外一方面.遞歸算法都可以轉(zhuǎn)化為非遞歸的算法
python里面也有變通的方法的


   

hmchzb19

回復 3# bskay


    你看2樓，我代碼寫錯了.

python 修改stack 的遞歸深度很簡單：
import sys
sys.setrecursionlimit(1000000)