递归函数[通俗易懂]
大家好，又见面了，我是你们的朋友全栈君。
如果一个函数在内部调用自身，这个函数就叫做递归函数
递归函数的简单定义如下：
代码语言：javascript代码运行次数：0运行复制def recursion():
return recursion()这只是一个简单的定义，什么也做不了。
当然，你可以尝试会发生什么结果，理论上会永远运行下去，但实际操作时发现不一会儿程序就报错了，因为每次调用函数都会用掉一点内存，在足够多的函数调用发生后，空间几乎被占满，程序就会报错。
代码语言：javascript代码运行次数：0运行复制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)用递归方式定义函数如下：
代码语言：javascript代码运行次数：0运行复制def fact(n):
if n==1:
return 1
return n*fact(n-1)执行该函数：
代码语言：javascript代码运行次数：0运行复制>>> fact(1)
1
>>> fact(5)
120
>>> fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L如果我们计算fact(5)，可以根据函数定义看到计算过程如下：
代码语言：javascript代码运行次数：0运行复制===> 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),执行结果如下：
代码语言：javascript代码运行次数：0运行复制RecursionError: maximum recursion depth exceeded in comparison由执行结果看到，执行出现异常，异常提示超过最大递归深度。
那么怎么解决这个问题呢？
首先我们可以通过修改最大递归深度来增加递归深度。通过sys模块的setrecursionlimit()方法来修改。
代码语言：javascript代码运行次数：0运行复制import sys
sys.setrecursionlimit(2000)#这样就可以增加最大递归深度但是这样也治标不治本，如果递归次数太多，那就说明这个问题就不适合用递归来解决。
还有一种方法，就是通过尾递归优化，事实上尾递归和循环的效果一样，把循环看成一种特殊尾递归函数也是可以的。
尾递归是指在函数返回时只能调用函数本身，return语句不能包含表达式，这样，编译器或解释器就可以对尾递归进行优化，使递归本身无论调用多少次都只占用一个栈帧，从而避免栈溢出的情况。
由于上面的fact(n)函数return n*(n-1)引入了乘法表达式，因此不是尾递归，要改成尾递归方式需要多一点代码，主要是把每一步乘积传入递归函数（通过把乘积结果传入函数参数的方式），看如下函数定义方式：
代码语言：javascript代码运行次数：0运行复制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)函数改成尾递归方式，也会导致栈溢出。
代码语言：javascript代码运行次数：0运行复制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但是可以通过装饰器方法手动进行尾递归优化，这里暂不叙述，详细方法百度
递归与三级菜单：
代码语言：javascript代码运行次数：0运行复制menu = {
'北京': {
'海淀': {
'五道口': {
'soho': {},
'网易': {},
'google': {}
},
'中关村': {
'爱奇艺': {},
'汽车之家': {},
'youku': {},
},
'上地': {
'百度': {},
},
},
'昌平': {
'沙河': {
'老男孩': {},
'北航': {},
},
'天通苑': {},
'回龙观': {},
},
'朝阳': {},
'东城': {},
},
'上海': {
'闵行': {
"人民广场": {
'炸鸡店': {}
}
},
'闸北': {
'火车战': {
'携程': {}
}
},
'浦东': {},
},
'山东': {},
} menu
代码语言：javascript代码运行次数：0运行复制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的地方， 递归函数实现三级菜单
代码语言：javascript代码运行次数：0运行复制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 用堆栈实现的三级菜单
二分查找法
代码语言：javascript代码运行次数：0运行复制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] 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