Python递归函数 二分查找算法实现解析
作者:changxin7 发布时间:2021-06-22 05:58:38
一、初始递归
递归函数:在一个函数里在调用这个函数本身。
递归的最大深度: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)+2
print(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 = 0
for 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('找不到')
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))
来源:https://www.cnblogs.com/changxin7/p/11340202.html
猜你喜欢
- 简介深度学习需要熟悉使用一个框架,本人选择了TensorFlow,一边学习一边做项目,下面简要介绍TensorFlow中的基本常量、变量和运
- 哪里出问题了python 中,使用 global 会将全局变量设为本函数可用。同时,在函数内部访问变量会先本地再全局。在嵌套函数中,使用 g
- 什么多态:同一事物有多种形态为何要有多态=》多态会带来什么样的特性,多态性多态性指的是可以在不考虑对象具体类型的情况下而直接使用对象多态指的
- 代理模式Proxy模式是一种常用的设计模式,它主要用来通过一个对象(比如B)给一个对象(比如A) 提供'代理'的方式方式访问
- SQL Server Sa用户相信大家都有一定的理解,下面就为您介绍SQL Server 2000身份验证模式的修改方法及SQL Serve
- FTP服务的主动模式和被动模式在开始之前,先聊一下FTP的主动模式和被动模式,两者的区别 , 用两张图来表示可能会更加清晰一些:主动模式:主
- 前言在日常工作中,常常需要周期性地执行某些任务,常用的方式是采用 Linux 系统自带的 crond 结合命令行实现,但最近却遇到了一个让人
- 今天用实验室的pycharm运行程序的时候发现出现了已安装的模块无法导入的情况,但实际上这个模块我已经在notebook中使用多次了,所以不
- 1.网页背景色的设置 犯错机率:很大普遍性:较广犯错可能性:懒/不知道约2年前我曾发现21cn上出现过一次没有设置背景色的情况,当时我用Em
- 引入为什么要有垃圾回收机制Python中的垃圾回收机制简称(GC),我们在程序的运行中会产生大量的变量用于保存数据,而有时候有些变量已经没有
- 一、anaconda的安装首先,下载安装包。Anaconda的下载方式有两种:通过官网下载,选择适合自己的电脑版本的安装包。https://
- 概述python开发过程中,我们可能需要同时开发多款应用,这些应用可能公用同一个版本的Python程序,但是使用不同版本的第三方库,比如A应
- 因为需要检测一个一个链接中是否包含了IP地址,在这里需要使用到正则表达式 ,python完美的支持了正则表达式,在这里使用re模块来完成,对
- 当使用Tensorflow训练大量深层的神经网络时,我们希望去跟踪神经网络的整个训练过程中的信息,比如迭代的过程中每一层参数是如何变化与分布
- 本文实例讲述了Python实例方法、类方法、静态方法的区别与作用。分享给大家供大家参考,具体如下:Python中至少有三种比较常见的方法类型
- 脚本语言的第一行的目的就是指出,你想要你的这个文件中的代码用什么可执行程序去运行它。写法:#!/usr/bin/python是告诉操作系统执
- 本文实例讲述了python获取各操作系统硬件信息的方法。分享给大家供大家参考。具体如下:1. windows使用WMI:(WMI官网地址:h
- 记得当时我们要跟网友天下合作,需要这样的一个鼠标划过放大的列表效果,就写了一个效果截图:演示代码:<!DOCTYPE html PUB
- Python是一种解释型、面向对象、动态数据类型的高级程序设计语言。Python由Guido van Rossum于 * 底发明,第一个
- 尽管Flask的request对象提供的支持足以处理web表单,但依然有许多任务会变得单调且重复。表单的HTML代码生成和验证提交的表单数据