函数递归调用介绍
函数不仅可以嵌套定义(即一个函数里面又定义了另外一个函数),而且可以嵌套调用,即一个函数调用了另外一个函数,甚至自己又调用了自己。
例如:
在调用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)
代码运行效果:

可以发现,代码进行两次函数,即可找到一个列表中是否存在某个值。
本文作者为blog,转载请注明。