大家好,又见面了,我是你们的朋友全栈君。
如果一个函数在内部调用自身,这个函数就叫做递归函数
递归函数的简单定义如下:
def recursion():
return recursion()
这只是一个简单的定义,什么也做不了。
当然,你可以尝试会发生什么结果,理论上会永远运行下去,但实际操作时发现不一会儿程序就报错了,因为每次调用函数都会用掉一点内存,在足够多的函数调用发生后,空间几乎被占满,程序就会报错。
RecursionError: maximum recursion depth exceeded
#超过最大递归深度
这类递归被称为无穷递归(infinite recursion),理论上永远都不会结束,当然,我们需要能实际做事情的函数,有用的递归函数应该满足如下条件:
(1)当函数直接返回值时有基本实例(最小可能性问题)
(2)递归实例,包括一个或多个问题最小部分的递归调用
使用递归的关键在于将问题分解为小部分,递归不能永远进行下去,因为它总是以最小可能性问题结束,而这些问题又存储在基本实例中。
函数调用自身怎么实现呢??
其实函数每次被调用时都会创建一个新的命名空间,也就是当函数调用‘自己’时,实际上运行的是两个不同的函数(也可以说一个函数具有两个函数的命名空间)。
我们来看一个递归示例,计算阶乘n!=1*2*3*4*5*……*n,用函数fact(n)表示,可以看出:
fact(n)=1*2*3*……*(n-1)*n=(n-1)!*n=fact(n-1)*n
所以,fact(n)可以表示为n*fact(n-1),只有n=1时需要特殊处理
于是,fact(n)用递归方式定义函数如下:
def fact(n):
if n==1:
return 1
return n*fact(n-1)
执行该函数:
>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L
如果我们计算fact(5)
,可以根据函数定义看到计算过程如下:
===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120
由函数定义可知,递归函数的有点是定义简单,逻辑清晰。
理论上,所有递归函数都可以写成循环的方式,不过循环的逻辑不如递归清晰。
使用递归函数需要注意仿制栈溢出,在计算机中,函数调用通过栈(stack)这种数据结构实现的。每当进入一个函数调用,栈就会增加一层栈帧,每当函数返回,栈就会减一层栈帧,忧郁栈的大小不是无线的,因此递归调用的次数过多会导致栈溢出。可以试试fact(1000),执行结果如下:
RecursionError: maximum recursion depth exceeded in comparison
由执行结果看到,执行出现异常,异常提示超过最大递归深度。
那么怎么解决这个问题呢?
首先我们可以通过修改最大递归深度来增加递归深度。通过sys模块的setrecursionlimit()方法来修改。
import sys
sys.setrecursionlimit(2000)#这样就可以增加最大递归深度
但是这样也治标不治本,如果递归次数太多,那就说明这个问题就不适合用递归来解决。
还有一种方法,就是通过尾递归优化,事实上尾递归和循环的效果一样,把循环看成一种特殊尾递归函数也是可以的。
尾递归是指在函数返回时只能调用函数本身,return语句不能包含表达式,这样,编译器或解释器就可以对尾递归进行优化,使递归本身无论调用多少次都只占用一个栈帧,从而避免栈溢出的情况。
由于上面的fact(n)函数return n*(n-1)引入了乘法表达式,因此不是尾递归,要改成尾递归方式需要多一点代码,主要是把每一步乘积传入递归函数(通过把乘积结果传入函数参数的方式),看如下函数定义方式:
def fact(n,ret=1):
if n==0:
return ret
return fact(n-1,ret=ret*n)
print(fact(5))#输出120
可以看到return fact(n-1,ret=ret*n)仅返回函数本身,n-1和ret=ret*n在函数调用前就会被计算,不影响函数的调用。
尾递归调用时,如果做了优化,栈不会增长,因此,无论多少次调用也不会导致栈溢出。
遗憾的是,大多数编程语言没有针对尾递归做优化,Python解释器也没有做优化,所以,即使把上面的fact(n)
函数改成尾递归方式,也会导致栈溢出。
def fact(n,ret=1):
if n==0:
return ret
return fact(n-1,ret=ret*n)
print(fact(1000))
#输出
RecursionError: maximum recursion depth exceeded in comparison
但是可以通过装饰器方法手动进行尾递归优化,这里暂不叙述,详细方法百度
递归与三级菜单:
menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
}
menu
def threeLM(dic):
while True:
for k in dic:print(k)
key = input('input>>').strip()
if key == 'b' or key == 'q':return key
elif key in dic.keys() and dic[key]:
ret = threeLM(dic[key])
if ret == 'q': return 'q'
threeLM(menu)
#会迷惑的一个地方就是当输入b和q时,返回key(此时key=b或q)是返回给上一次return的地方,
递归函数实现三级菜单
l = [menu]
while l:
for key in l[-1]:print(key)
k = input('input>>').strip() # 北京
if k in l[-1].keys() and l[-1][k]:l.append(l[-1][k])
elif k == 'b':l.pop()
elif k == 'q':break
用堆栈实现的三级菜单
二分查找法
lis=[2,3,5,10,15,16,18,22,26,30,32,35,41,42,43,55,56,66,67,69,72,76,82,83,88]
def find(aim,li,start=0,end=None):
end=len(li) if end is None else end
middle=(end-start)//2+start
if start<=end:
if li[middle]>aim:
return find(aim,li,start=start,end=middle-1)
elif li[middle]<aim:
return find(aim,li,start=middle+1,end=end)
else:
return middle
else:
return 'not find'
print(find(16,lis))
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/154826.html原文链接:https://javaforall.cn