为什么我这个递归的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在后台维护了很多资源,比如调用栈需要很多的属性,每个属性可能又有很多属性....
就是最基本的属性,对应到C/C++上面是要占用不少内存等资源的....
实际用的资源就很多了

另外一方面.递归算法都可以转化为非递归的算法
python里面也有变通的方法的


   

hmchzb19

回复 3# bskay


    你看2楼，我代码写错了.

python 修改stack 的递归深度很简单：
import sys
sys.setrecursionlimit(1000000)