在python中,如阶乘运算,函数的自身循环调用等叫做递归。
递归主要有递推和回溯两个阶段。
递归的效率低,需要在进入下一次递归时,保留当前的状态,解决方法是尾递归,即在函数的最后一步(而非最后一行)调用自己。但是python没有尾递归,且对递归层级做了限制
1.必须有一个明确的结束条件
2.每次进入更深一层递归时,问题规模相比山此递归应有所减少
3.递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以递归调用的次数过多,会导致栈溢出)
在默认情况下,系统会对递归做层级的限制,默认是1000:
>>> import sys
>>> sys.getrecursionlimit()
1000
当然,我们也可以修改这个值:
>>> sys.setrecursionlimit(500)
>>> sys.getrecursionlimit()
500
当然不推荐修改。
递归的使用
循环和递归具有相似的功能,但是在有些场景下,我们无法指定循环的条件时,使用递归就能很好的是实现.
如,打印出列表中的所有数字:
a=[1,[2,[3,[4,[5,[6,[7,[8,[9,10,11],12]]]]]]]]
def list_num(list_n):
for i in list_n:
if type(i) is list:
list_num(i)
else:
print(i)
list_num(a)
二分法
在使用递归对有序数列进行查找时,使用二分法可以极大的提高算法效率。二分法的的原理是每次都截取一半,在这一半中查找需要的值。这里使用递归:
a=[0, 1, 2, 3, 6, 7, 8, 9, 33, 44, 54, 66, 67, 878]
def findnum(num,l):
print(l)
if len(l)==1:
if l[0] == num:
print('find this num')
else:
print('not exist')
return
half_index=len(l)//2
if num == l[half_index]:
print('find this num')
return
elif num > l[half_index]:
l=l[half_index:]
elif num < l[half_index]:
l=l[:half_index]
findnum(num, l) # 使用递归调用自身
findnum(34,a)
网友评论