Python函数递归和二分法

函数递归调用介绍

函数不仅可以嵌套定义(即一个函数里面又定义了另外一个函数)，而且可以嵌套调用，即一个函数调用了另外一个函数，甚至自己又调用了自己。

例如：

在调用bar()函数的时候，bar()函数的内部又调用了自己

def bar():
	print('helloworld')
	bar()
bar()

其调用关系如上图所示，可以看到，这是一个类似于死循环的调用，类似于直接是while True: bar(),当函数外部调用了bar()，则会执行函数内部的内容，此时函数内部又调用了bar()，之后又运行了bar()函数，则又执行了函数内部的bar()调用。周而复始，所以是循环调用了。

但是，对于这种循环调用，Python解释器并不会惯着他，并不会真的让他一直循环调用，这个是有限制的。可以通过sys模块中的getrecursionlimit()方法查询。

可以看到，默认的函数递归调用为1000次，超过1000次，则会直接报错。

实际调用的时候，我这里其实只调用了992次。

我们可以通过sys模块下的setrecursionlimit()方法， 修改递归调用限制的次数。

修改递归调用的次数之后，可以发现，再次运行递归函数的时候，运行次数明显为20次左右。实际为17次。

其实递归的本质就是循环，需要强调的是递归不应该无限地调用下去，必须在满足某种情况下结束递归，而递归的是一个函数，while循环的话，结束循环使用break关键字即可，而对于函数，则使用return，那么return后的代码即可终止一个函数的运行。

# 使用函数递归,打印出10以内的数字，不得使用for或while循环

def add(n):
	n = n + 1
	if n == 10:
		return 
	print(n) 
	add(n)
add(0)

当一个函数执行return之后，那么该函数就会终止运行。

函数递归的两个阶段

回溯：一层一层的调用下去

递推：满足某种结束条件，结束递归调用，之后一层一层的返回。

下面我们举个例子，为了让同学，更深层次的区了解回溯和递推。

假设五个人坐在一起，然后第一个人问第二个人的年龄是多大，第二个人回答，我比第三个人大10岁，之后第一个人，要想知道第二个人多大，就必须知道第三个人的岁数，所以要去问第三个人，而第三个人说，我比第四个人的岁数大10岁。那么我们还需要去问第四个人的岁数，而第四个人说，它是第五个人岁数+10，这时，才可以知道第二个人的岁数，这是一个关系型的。

'''
数学表达式分析
age(5) = age(4) + 10
age(4) = age(3) + 10
age(3) = age(2) + 10 
age(2) = age(1) + 10
age(1) = 19
'''

Python语句书写：

def age(n):
	if n == 1:
		return 19
	return age(n - 1) + 10

print(age(4)) # 49

递归的应用

使用函数的递归将如下列表的值取出来

# 将如下嵌套列表的值逐个取出
l = [1,[2,3,[4,5,[6,[7,[9,10,11,[20,30,40,['x1ong','lulu',[1000,100,'一百']]]]]]]]]


def f1(list1):
	for i in list1:
		if type(i) is list:
			f1(i)
		else:
			print(i)

f1(l)s

二分法

假设有如下需求，我们需要从一个从小到大排序的的列表中，找出一个值是否存在于该列表中，如何去查找呢？

# 查找一个从小到大的列表中是否存在某个值


# 方法一：使用for循环遍历，之后使用if判断
l = [1,3,5,7,9,11,13,15,17,19,21,23,25,99,67,83]

find_num = 9

target_index = 0
for i in l:
	if find_num == i:
		print('extsience',target_index)
	else:
		target_index += 1

可以看到，这个的确可以查询出一个数值，是否存在一个列表中，但是这样的做法并不高效，首先这个列表是一个有规律的列表，它是从小到大进行排序的，那么我们就可以利用该特点，去高效的查找我们想要的值。

我们可以使用二分法算法，将这个列表拆分为两半，由于列表是从小到大的列表，所以我们可以进行比较。

算法则是高效解决问题的方法。

以下为在使用二分法之前的逻辑推导式：

'''
# 查找一个丛小到大的列表中是否存在某个值

l = [1,3,5,7,9,11,13,15,17,19,21,23,25,99,67,83]

find_num = 9

def dichotmny(find_num,列表): # 定义一个函数，接受两个参数，参数1为要查找的值，参数2为数据列表
	mid_value = 列表的中间值
	if find_num > 列表[mid_value]:
		# 接下来就要查找列表的右半部分
		列表 = 列表切片右半部分
		dichotmny(find_num,列表)
	elif find_num < 列表[mid_value]:
		# 接下来就要查找列表的左半部分
		列表 = 列表切片左半部分
		dichotmny(find_num,列表)
	else:
		print('find it')
'''

那么，我们将逻辑推导式变现为Python代码，就为如下：

 
l = [1,3,5,7,9,11,13,15,17,19,21,23,25,99,67,83]
 
find_num = 99
 
def dichotmny(find_num,list1):
	print(list1) 
	if len(list1) == 0: # 如果最后返回的列表长度为0，直接终止函数运行即可，则直接终止函数
		return 
	mid_value = len(list1) // 2  # 将列表的长度整除以2,即可得到中间的值
	if find_num > list1[mid_value]:
		list1 = list1[mid_value + 1:]  # 列表切片右半部分 顾头不顾尾,所以要+1
		dichotmny(find_num,list1) # 再次判断
	elif find_num < list1[mid_value]:
		list1 = list1[:mid_value] # 列表切片左半部分
		dichotmny(find_num,list1)
	else:
		print('find it') # 如果找到该值则打印出find it
dichotmny(find_num,l)

代码运行效果：

可以发现，代码进行两次函数，即可找到一个列表中是否存在某个值。