Python 递归函数、二分法

递归函数：

在函数运行过程中，如果没有达到终止条件，就再次调用自己，直到达到终至条件或者程序结束。

最大递归层数：默认为1000，根据电脑硬件（cpu）或者系统不同，也可能在998左右停止。

查看最大递归深度：sys.getrecursionlimit()

设置最大递归深度：sys.setrecursionlimit(2000)

递归包含两个过程：

一是先嵌套推导，推导时每一层的复杂度要降低

二是后回溯返回。

l = [1,[2,[3,[4,[5,[6,[7,[8,[9,[10,[11,[12,[13,[14,]]]]]]]]]]]]]]

打印上面列表中的每个数字：

def printnum(l):

　　for i in l:

　　　　if type(i) is int:

　　　　　　print(i)

　　　　elif type(i)  is list:

　　　　　　printnum(i)

二分法：一种快速查找算法。

前提：数据是按从小到大的顺序排序的。

方法：每次取全部数据 数量的中间值，与要查找的目标数值做比较，

　　如果中间值比目标值大，侧再次取左边部分的中间值进行比较，

　　如果中间值比目标值小，侧取右边部分的中间值与目标值进行比较，依次类推。

优先：大大减少比较次数（对数级减少）

缺点：当目标值的位置比较靠前时，查找的资料反而变多。

程序：递归法。

例：

l = [11, 22, 33, 44, 55, 66, 88, 99, 101, 123, 154, 165, 175, 413, 465, 498, 500, 565]

def e(a,num):
　　midnum = len(a)//2
　　if a[midnum] > num:
　　　　left = a[:midnum]
　　　　e(left,num)
　　elif a[midnum] < num:
　　　　right = a[midnum + 1 :]
　　　　e(right,num)
　　elif a[midnum] == num:
　　　　print(num,"at %s "%midnum)

printnum(l,a)