Python递归函数,二分查找算法简介

作者 : shijian 本文共2650个字,预计阅读时间需要7分钟 发布时间: 2019-08-12 共75人阅读

一、初始递归

  递归函数:在一个函数里在调用这个函数本身。

  递归的最大深度:998

  正如你们刚刚看到的,递归函数如果不受到外力的阻止会一直执行下去。但是我们之前已经说过关于函数调用的问题,每一次函数调用都会产生一个属于它自己的名称空间,如果一直调用下去,就会造成名称空间占用太多内存的问题,于是python为了杜绝此类现象,强制的将递归层数控制在了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层递归都没有解决的问题要么是不适合使用递归来解决要么是你代码写的太烂了~~~

  看到这里,你可能会觉得递归也并不是多么好的东西,不如while True好用呢!然而,江湖上流传这这样一句话叫做:人理解循环,神理解递归。所以你可别小看了递归函数,很多人被拦在大神的门槛外这么多年,就是因为没能领悟递归的真谛。而且之后我们学习的很多算法都会和递归有关系。来吧,只有学会了才有资本嫌弃!

二、递归示例讲解

  这里我们又要举个例子来说明递归能做的事情。

  例一:

  现在你们问我,alex老师多大了?我说我不告诉你,但alex比 egon 大两岁。

  你想知道alex多大,你是不是还得去问egon?egon说,我也不告诉你,但我比武sir大两岁。

  你又问武sir,武sir也不告诉你,他说他比太白大两岁。

  那你问太白,太白告诉你,他18了。

  这个时候你是不是就知道了?alex多大?

1 金鑫 18
2 武sir 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]

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

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

827651-20170730200049162-1549215684.png

  这就是二分查找算法!

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

  简单版二分法

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('找不到')
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 '没有此值'
    else:
         return '没有此值'
print(two_search(l1,9))

以上就是Python递归函数,二分查找算法简介的详细内容,更多请关注吆喝资源网其它相关文章!

吆喝资源网最新课程二维码

  • 相关标签:python 递归函数 二分查找算法
  • 本文转载于:博客园,如有侵犯,请联系删除
  • 本文转自PHP中文网,吆喝网(http://yaoohe.com)搜集整理,如有疑问请联系本站客服!

    1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
    2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
    3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
    4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
    5. 如有链接无法下载、失效或广告,请联系管理员处理!
    6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
    7. 如遇到加密压缩包,默认解压密码为"yaoohe.com",如遇到无法解压的请联系管理员!
    吆喝资源网 » Python递归函数,二分查找算法简介

    常见问题FAQ

    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。 若排除这种情况,可在对应资源底部留言,或 联络我们。

    发表评论