python中的递归
关注公众号“轻松学编程”了解更多。
文章更改后地址：传送门
间接或直接调用自身的函数被称为递归函数。
间接：
def func():
otherfunc()
def otherfunc():
func()
直接：
def func():
func()
递归函数必须要有收敛条件和递归公式。
1、递归求和
'''
使用递归求和
'''
def my_sum(n):
'''
递归求和
1+2+3+...+n
:param n: int型
:return: int型
'''
# 收敛条件
if n == 1:
return 1
# 递归公式
return n + my_sum(n-1)
def main():
print(my_sum(10))
if __name__ == '__main__':
main()
结果为：
55
当发生函数调用时 需要做保存现场和恢复现场的工作。
保存现场和恢复现场的工作都是利用栈(stack)来实现的。
栈是一个FILO的结构 - 栈非常的快但是它很小。
python默认栈的层数为1000层，可以使用以下方法来增加层数(不推荐)
import sys
# 比如增加层数到9999层
sys.setrecursionlimit(9999)
这样的递归不好，因为递归使用的是栈，需要用栈来保护现场和恢复现场，很耗费资源，可以使用尾递归来解决这个问题，即不回溯，直接使用最后一次的结果作为最终的结果。
2、尾递归
'''
使用递归求和
'''
def my_sum(n,result=0):
'''
递归求和
1+2+3+...+n
:param n: int型
:param result: int型,上一层求得的结果，第一层递归时为0
:return: int型
'''
# 收敛条件
if n == 1:
return result +1
# 递归公式
return my_sum(n-1,result=result+n)
def main():
print(my_sum(10))
if __name__ == '__main__':
main()
结果为：
55
3、递归求斐波那契数列
'''
斐波那契数列：
f(n) = 1 当n = 1,2时
f(n) = f(n-1) + f(n-2) 当n > 2时
比如： [1,1,2,3,5,8,13,21,34,55]
'''
def fibonacci(n):
# 收敛条件
if n <= 2:
return 1
# 递归公式
return fibonacci(n-1) + fibonacci(n-2)
def main():
print(fibonacci(10))
if __name__ == '__main__':
main()
结果为：
55
这样的递归是不好的，因为每求一层递归都要重新计算前面(n-1)层递归，开销很大，比如:
求f(9)
要先求f(8) + f(7)
而f(8)= f(7) + f(6)
f(7)=f(6) + f(5)
...
为了节省这部分重复的开销，可以使用动态规划来解决这个问题。
4、动态规划实现递归
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
在python中的递归，可以使用字典来代替这个表。
'''
斐波那契数列：
f(n) = 1 当n = 1,2时
f(n) = f(n-1) + f(n-2) 当n > 2时
比如： [1,1,2,3,5,8,13,21,34,55]
'''
def fibonacci(n,temp={ }):
# 收敛条件
if n <= 2:
return 1
# 首先先从字典中取值
try:
return temp[n]
except KeyError:
# 如果字典中没有就先把值存进字典
temp[n] = fibonacci(n-1) + fibonacci(n-2)
return temp[n]
def main():
print(fibonacci(10))
if __name__ == '__main__':
main()
结果为：
55
使用动态规划解决：
一个小孩爬阶梯，一次有3种走法：一次走1个阶梯，一次走2个阶梯，一次走3个阶梯，问如果有10个阶梯总共有多少中走法？
def walk(steps,temp={}):
if steps < 0:
return 0
elif steps == 0:
return 1
try:
return temp[steps]
except KeyError:
temp[steps] = walk(steps - 1) + walk(steps - 2) + walk(steps - 3)
return temp[steps]
print(walk(10))
结果为：
274
5、使用装饰器测试递归函数用时
'''
斐波那契数列：
f(n) = 1 当n = 1,2时
f(n) = f(n-1) + f(n-2) 当n > 2时
比如： [1,1,2,3,5,8,13,21,34,55]
'''
from functools import wraps
import time
def func_time(func):
# 使用@wraps后可以还原原来的函数
# 即可以使用func.__wrapped__()来去掉装饰器
@wraps(func)
def wrapper(*arg,**kwargs):
# 第一层递归才输出时间
if kwargs['level'] == 0:
start = time.perf_counter()
result = func(*arg,**kwargs)
end = time.perf_counter()
print(f'Execution Time:{end-start}s')
return result
else:
return func(*arg,**kwargs)
return wrapper
@func_time
def fibonacci(n,temp={},*,level):
# 收敛条件
if n <= 2:
return 1
# 首先先从字典中取值
try:
return temp[n]
except KeyError:
level += 1
# 如果字典中没有就先把值存进字典
temp[n] = fibonacci(n-1,level=level) + fibonacci(n-2,level=level)
return temp[n]
def main():
print(fibonacci(121, level=0))
fib_19 = fibonacci.__wrapped__(19,level=0)
fib_20 = fibonacci.__wrapped__(20,level=0)
print(f'黄金比例:{fib_19/fib_20}')
if __name__ == '__main__':
main()
结果为：
Execution Time:0.0012316425773240605s
8670007398507948658051921
黄金比例:0.6180339985218034
注意1：能用循环写的代码一定不要使用递归。
注意2：如果用递归也尽量使用尾递归(只需要递归不需要回溯)和动态规划。
后记
【后记】为了让大家能够轻松学编程，我创建了一个公众号【轻松学编程】，里面有让你快速学会编程的文章，当然也有一些干货提高你的编程水平，也有一些编程项目适合做一些课程设计等课题。
也可加我微信【1257309054】，拉你进群，大家一起交流学习。
如果文章对您有帮助，请我喝杯咖啡吧！
公众号
关注我，我们一起成长~~