Python recursive function, introduction to binary search algorithm

1. Initial recursion

Recursive function: Call the function itself within a function.

Maximum depth of recursion: 998

As you just saw, the recursive function will continue to execute if it is not blocked by external forces. But we have already talked about the problem of function calls before. Each function call will generate a name space of its own. If it is called continuously, it will cause the name space to occupy too much memory, so Python is trying to prevent this kind of phenomenon. , forcibly controlling the number of recursion levels to 997 (as long as 997! You can’t suffer losses or be fooled...).

What can be used to prove this "998 theory"? Here we can do an experiment:

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

From this we can see that the maximum number that can be seen before an error is reported is 998. Of course, 997 is a number set by python for the memory optimization of our program. Default value, of course we can also modify it through some means:

import sys
print(sys.setrecursionlimit(100000))

We can modify the maximum depth of recursion in this way. We just set the recursion depth allowed by python to 10w. As for the actual recursion depth, it can be reached The depth depends on the performance of the computer. However, we still do not recommend changing this default recursion depth, because if the problem cannot be solved with 997 levels of recursion, it is either not suitable to use recursion to solve it, or your code is too poorly written~~~

Look At this point, you may feel that recursion is not such a good thing, and it is not as useful as while True! However, there is a saying circulating in the world: humans understand cycles, gods understand recursion. So don’t underestimate recursive functions. Many people have been blocked from the threshold of great masters for so many years because they failed to understand the true meaning of recursion. And many of the algorithms we learn in the future will be related to recursion. Come on, only if you learn it will you have the capital to dislike it!

2. Recursive example explanation

Here we will give another example to illustrate what recursion can do.

Example 1:

Now you ask me, how old is Mr. Alex? I said I won't tell you, but Alex is two years older than egon.

If you want to know how old Alex is, do you still have to ask Egon? egon said, I won’t tell you either, but I am two years older than Sir Wu.

You asked Sir Wu again, but Sir Wu didn’t tell you either. He said he was two years older than Taibai.

Then you ask Taibai, Taibai will tell you that he is 18.

Did you know it at this time? How old is alex?

　　你为什么能知道的？

　　首先，你是不是问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))

The above is the detailed content of Python recursive function, introduction to binary search algorithm. For more information, please follow other related articles on the PHP Chinese website!