递归就是在函数的执行过程中调用自己
import sys print(sys.getrecursionlimit()) #python的最大递归深度 1000
import sys print(sys.getrecursionlimit()) #python的最大递归深度 1000 sys.setrecursionlimit(1500) #可以设置最大递归深度
递归与栈的关系
递归的作用
def func(n): v= n//2 print(v) if v == 0 : return v else: func(v) func(10)
结果:
5
2
1
0
#递归函数 def func(n): v= n//2 print(v) if v == 0 : return v func(v) print(v) func(10)
运行结果:
5
2
1
0
1
2
5
递归的几个特点:
1.必须有一个明确的结束条件
2.每次进入更深一层递归时,问题规模相比上次递归应由所减小
3.递归的效率不高,递归层次过多会出现栈溢出。
递归有什么用?
可以用于解决很多算法问题,把复杂的问题分成一个个小问题,一一解决
比如求斐波那契数列、汉诺塔、多级评论数、二分查找、求阶乘等。
#求阶乘 def fac(n): if n == 1: return 1 else: return n * fac(n-1) print(fac(3))
尾递归优化:
#尾递归 def cal(n): print(n) return cal(n+1)
python里没有做尾递归优化
二分查找
#二分查找 def binary_search(alist,data): lenth = len(alist) if lenth <1 : return False mid = lenth //2 if data > alist[mid]: return binary_search(alist[mid+1:],data) elif data < alist[mid]: return binary_search(alist[0:mid],data) else: return True list = [2,3,6,7,10,23,57] print(binary_search(list,60))