Python 재귀 함수, 이진 검색 알고리즘 소개

1. 초기 재귀

재귀 함수: 함수 내에서 함수 자체를 호출합니다.

　 최대 재귀 깊이: 998

　 방금 본 것처럼 재귀 함수는 외부 힘에 의해 차단되지 않으면 계속 실행됩니다. 하지만 함수 호출의 문제에 대해서는 이미 이야기한 적이 있는데, 함수를 호출할 때마다 자신만의 네임스페이스가 생성되기 때문에 계속해서 호출하면 네임스페이스가 너무 많은 메모리를 차지하는 문제가 발생하게 됩니다. 이런 현상을 방지하기 위해 재귀 레벨 수를 997로 강제 제어합니다(997까지! 손실을 입거나 속아서는 안 됩니다...).

이 "998 이론을 증명할 수 있는 것은 무엇입니까?" "? 여기서 우리는 실험을 할 수 있습니다:

def foo(n):
    print(n)
    n += 1
    foo(n)
foo(1)

이것으로부터 우리는 오류가 보고되기 전에 볼 수 있는 최대 숫자가 998이라는 것을 알 수 있습니다. 물론 997은 우리 프로그램의 메모리 최적화를 위해 Python이 설정한 기본값입니다. 물론, 다음과 같은 방법으로 수정할 수도 있습니다:

import sys
print(sys.setrecursionlimit(100000))

이 방법으로 최대 재귀 깊이를 수정할 수 있습니다. Python에서 허용하는 재귀 깊이를 10w로 설정하면 됩니다. 그것은 컴퓨터의 성능에 따라 달라집니다. 그러나 997 수준의 재귀로 해결할 수 없는 문제가 재귀로 해결하기에 적합하지 않거나 코드가 너무 형편없게 작성된 경우에는 여전히 기본 재귀 깊이를 변경하지 않는 것이 좋습니다 ~~

여기를 참조하세요, 당신은 재귀가 그렇게 좋은 것이 아니며 True만큼 유용하지 않다고 생각할 수도 있습니다! 그러나 세상에는 인간은 순환을 이해하고 신은 순환을 이해한다는 말이 있습니다. 그러므로 재귀 함수를 과소평가하지 마십시오. 많은 사람들이 재귀의 진정한 의미를 이해하지 못했기 때문에 수년 동안 대가의 문턱에서 차단되었습니다. 그리고 우리가 앞으로 배울 알고리즘 중 상당수는 재귀와 관련이 있을 것입니다. 어서, 배워야 만 그것을 싫어할 자본이 생길 것입니다!

2. 재귀 예제

여기서는 재귀가 무엇을 할 수 있는지 설명하기 위해 또 다른 예를 들어보겠습니다.

　예 1:

이제 물어보시죠. Alex 씨는 몇 살입니까? 말하지 않겠다고 했는데 알렉스는 에곤보다 두 살 연상이다.

　알렉스가 몇 살인지 알고 싶으면 이곤에게 물어봐야 하나요? 에곤은 "나도 말 안 하겠지만 내가 우경보다 두 살 많다"고 말했다.

당신이 우 경에게 다시 물었지만 우 경도 당신에게 타이바이보다 2살 더 많다고 말하더군요.

그리고 타이바이에게 물어보면 타이바이는 18살이라고 대답할 거예요.

이때 알고 계셨나요? 알렉스는 몇 살이에요?

1	金鑫	18
2	무 선생님	20
3	egon	22
4	alex	24

　　你为什么能知道的？

　　首先，你是不是问alex的年龄，结果又找到egon、武sir、太白，你挨个儿问过去，一直到拿到一个确切的答案，然后顺着这条线再找回来，才得到最终alex的年龄。这个过程已经非常接近递归的思想。我们就来具体的我分析一下，这几个人之间的规律。

age(4) = age(3) + 2 
age(3) = age(2) + 2
age(2) = age(1) + 2
age(1) = 40

　　那这样的情况，我们的函数怎么写呢？

def age(n):
    if n == 1:    
      return 40
    else:     
         return age(n-1)+2print(age(4))

　　如果有这样一个列表，让你从这个列表中找到66的位置，你要怎么做？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

　　你说，so easy！

　　l.index(66)...

　　我们之所以用index方法可以找到，是因为python帮我们实现了查找方法。如果，index方法不给你用了。。。你还能找到这个66么？

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
i = 0for num in l:    if num == 66:
        print(i)
    i+=1

　　上面这个方法就实现了从一个列表中找到66所在的位置了。

　　但我们现在是怎么找到这个数的呀？是不是循环这个列表，一个一个的找的呀？假如我们这个列表特别长，里面好好几十万个数，那我们找一个数如果运气不好的话是不是要对比十几万次？这样效率太低了，我们得想一个新办法。

二分查找算法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]

　　你观察这个列表，这是不是一个从小到大排序的有序列表呀？

　　如果这样，假如我要找的数比列表中间的数还大，是不是我直接在列表的后半边找就行了？

　　这就是二分查找算法！

　　那么落实到代码上我们应该怎么实现呢？

　　简单版二分法

l = [2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]def func(l,aim):
    mid = (len(l)-1)//2
    if l:        if aim > l[mid]:
            func(l[mid+1:],aim)        elif aim < l[mid]:
            func(l[:mid],aim)        elif aim == l[mid]:
            print("bingo",mid)    else:
        print(&#39;找不到&#39;)
func(l,66)
func(l,6)

　　升级版二分法

l1 = [1, 2, 4, 5, 7, 9]
def two_search(l,aim,start=0,end=None):
    end = len(l)-1 if end is None else end
    mid_index = (end - start) // 2 + start    
    if end >= start:
            if aim > l[mid_index]:
                        return two_search(l,aim,start=mid_index+1,end=end
             elif aim < l[mid_index]:
                 return two_search(l,aim,start=start,end=mid_index-1)        
             elif aim == l[mid_index]:
                 return mid_index        
             else:
                 return &#39;没有此值&#39;
    else:
         return &#39;没有此值&#39;
print(two_search(l1,9))

위 내용은 Python 재귀 함수, 이진 검색 알고리즘 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!