Python中的递归函数及二分查找算法如何使用？

w8484855@qq.com

本文和大家分享的主要是python的递归函数及二分查找算法相关内容，一起来看看吧，希望对大家学习python有所帮助。

　　一、递归的定义

　　def story():

　　s = """

　　从前有个山，山里有座庙，庙里老和尚讲故事，

　　讲的什么呢？

　　"""

　　print(s)

　　story()

　　story()

　　老和尚讲故事

　　递归的定义 —— 在一个函数里再调用这个函数本身。这种魔性的使用函数的方式就叫做 递归 。

　　递归的最大深度：997

　　1、python递归最大层数限制 997

　　2、最大层数限制是python默认的，可以做修改

　　3、但是我们不建议你修改

　　n = 0def f():

　　global n

　　n += 1

　　print(n)

　　f()

　　f()

　　测试递归最大深度

　　如何修改递归最大深度：

　　import sys #所有和python相关的设置和方法

　　sys.setrecursionlimit(10000000)

　　n = 0def f():

　　global n

　　n += 1

　　print(n)

　　f()

　　f()

　　修改递归最大深度

　　递归的小实践：

　　1、猜年龄：

　　#猜e的年龄#e比d大两岁#d比c大两岁#c比b大两岁#b比a大两岁 #a 40了

　　# 1.a  age(1) = 40# 2.b  age(1) + 2# 3.c   age(2) + 2# 4.d  age(3) + 2# 5.e  age(4) + 2

　　def age(n):

　　if n == 1:

　　return 40

　　else:

　　ret = age(n-1)

　　return ret + 2

　　age(5)

　　猜年龄

　　2 、 一个数，除2到不能整除2为止：

　　#一个数，除2到不能整除2为止（以8为例）def cal(num):

　　if num % 2 == 0:

　　num  = num // 2

　　return cal(num)

　　else:

　　return num

　　print(cal(8))

　　数字整除类1

　　3、整除类2

　　#如果一个数 可以整除2 就整除#不能整除就*3+1def func(num):

　　print(num)

　　if num == 1:

　　return

　　if num %2 == 0:

　　num = num //2

　　else:

　　num = num * 3 + 1

　　func(num)

　　func(5)

　　数字整除类2

　　递归函数与三级菜单

　　递归函数实现三级菜单

　　二、二分查找算法

　　给你一个数列让你找出其中一个数的位置你怎么找？index？这是python给我们的内置函数。那他内部是怎么实现的呢？现在要求我们自己设计函数来实现这个功能。

　　数列例如： 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]

　　i = 0for num in l:

　　if num == 66:

　　print(i)

　　i+=1

　　是不是感觉这个函数so easy但是我们所用的方法是循环列表然后一个一个对比。这个方法固然可以可是也只是适用于小的数组。如果这个数列很长里面上万甚至更多，一个一个找效率太低。必须有一个新的算法来解决这个问题。这就引出了今天另一个知识点 二分查找

　　二分查找算法:

　　算法：计算的方法

　　二分查找前提：有序的递增列表

　　图示：

这就是二分查找算法

　　简单二分法：

　　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)

　　二分法基础版

　　二分法升级：

　　def func(l, aim,start = 0,end = len(l)-1 ):

　　mid = (start+end)//2

　　if not l[start:end+1]:

　　return

　　elif aim > l[mid]:

　　return func(l,aim,mid+1,end)

　　elif aim < l[mid]:

　　return func(l,aim,start,mid-1)

　　elif aim == l[mid]:

　　print("bingo")

　　return mid

　　index = func(l,68)

　　print(index)

　　二分法查找升级版

　　小结：

　　递归解决的问题：

　　就是通过参数，来控制每一次调用缩小计算的规模

　　适合的场景：

　　数据的规模在减小，但是解决问题的思路没有改变

　　结束递归的标志：return

来源：博客园