Python函数递归和二分法

函数递归调用介绍

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

例如:

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

def bar():
	print('helloworld')
	bar()
bar()
Python函数递归和二分法插图

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

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

Python函数递归和二分法插图1

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

Python函数递归和二分法插图2

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

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

Python函数递归和二分法插图3

修改递归调用的次数之后,可以发现,再次运行递归函数的时候,运行次数明显为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
Python函数递归和二分法插图4

递归的应用

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

# 将如下嵌套列表的值逐个取出
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)

代码运行效果:

Python函数递归和二分法插图5

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

本文作者: x1ong
免责声明:本博客所有文章仅用于学习交流
转载声明:文章为作者原创文章 转载请注明来源
本文链接: https://www.giaoblog.com/python/22599.html
上一篇
下一篇