正文
Python入门篇-递归函数Recursion
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Python入门篇-递归函数（recursion）
作者：尹正杰
版权声明：原创作品，谢绝转载！否则将追究法律责任。
一.递归概述
（1）函数直接或者间接调用自身就是递归；
（2）递归需要有边界，递归前进段，递归返回段；
（3）递归一定要有边界条件；
（4）当边界条件不满足的时候，递归前进；
（5）当边界条件满足的时候，递归返回；
二.递归案例
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.com import sys print("默认的递归调用次数限制0是：{} 次".format(sys.getrecursionlimit())) sys.setrecursionlimit(20000) #我们修改默认的递归调用次数 print("当前递归调用次数限制是：{} 次".format(sys.getrecursionlimit()))
"""
递归要求：
递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用。
递归调用的深度不宜过深：
Python对递归调用的深度做了限制，以保护解释器
超过递归深度限制，抛出："RecursionError： maxinum recursion depth exceeded" 即超过了最大递归深度
sys.getrecursionlimit()
""" """
斐波拉契数字推理公式：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
"""
def fib(n):
return 1 if n < 2 else fib(n-1) + fib(n-2) for i in range(20):
print(fib(i), end=' ') #以上代码执行结果如下:
默认的递归调用次数限制0是：1000 次
当前递归调用次数限制是：20000 次
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
三.递归的性能
1>.使用for循环打印斐波拉契前35个数字
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.com import datetime start = datetime.datetime.now() pre = 0 cur = 1 # No1 print(pre, cur, end=' ') n = 35 for i in range(n-1):
pre, cur = cur, pre + cur
print(cur, end=' ') delta = (datetime.datetime.now() - start).total_seconds() print("\n递归调用打印斐波拉契钱35个数字的时间为：{}".format(delta)) #以上代码直接结果如下:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465
递归调用打印斐波拉契钱35个数字的时间为：0.0
2>.使用递归方式打印斐波拉契前35个数字
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.com import datetime n = 35 start = datetime.datetime.now() def fib(n):
return 1 if n < 2 else fib(n-1) + fib(n-2) for i in range(n):
print(fib(i), end=' ') delta = (datetime.datetime.now() -start).total_seconds() print("\n递归调用打印斐波拉契钱35个数字的时间为：{}".format(delta)) #以上代码直接结果如下:
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465
递归调用打印斐波拉契钱35个数字的时间为：5.93134
3>.递归优化方案
循环稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果fib函数代码极简易懂，但是只能获取到最外层的函数调用，内部递归都是中间结果。而且给定一个n都要进行2n次递归，深度月神，效率月底。为了获取斐波那契数列需要外面在套一个n次的循环，效率就更低了。递归还有深度限制，如果递归复杂，函数反复压栈，栈内存很快就溢出了思考：这个极简的递归代码能否提高性能呢？下面是优化后的代码，效率有明显的提示，代码如下所示：
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comimport datetimestart = datetime.datetime.now()pre = 0cur = 1 # No1print(pre, cur, end=' ')"""
改进后的fib函数和循环的思想类似
参数n是边界条件，用n来计算
上一次的结果直接作为参数的实参
效率很高
和循环比较，性能相近。所以并不是说递归一定效率低下。但是递归有深度限制。
"""
def fib(n, pre=0,cur=1): # recursion
pre, cur = cur, pre + cur
print(cur, end=' ')
if n == 2:
return
fib(n-1, pre, cur)fib(35)delta = (datetime.datetime.now() -start).total_seconds()print("\n递归调用打印斐波拉契钱35个数字的时间为：{}".format(delta))#以上代码直接结果如下:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465
递归调用打印斐波拉契钱35个数字的时间为：0.0
4>.间接递归
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comdef foo():
bar()def bar():
foo()"""
我们这里看起来只是调用foo函数，但是进入foo函数中的函数体中我们发现调用bar函数，进入bar函数中的函数体中我们发现它
又再次调用foo函数。因此我们执行该代码后会发现跑出来异常：“RecursionError: maximum recursion depth exceeded”.
这就形成了间接递归，是通过别的函数调用了函数自身。但是，如果构成了循环递归调用是非常危险的，但是往往这种情况在代码
复杂的情况下，还是可能发生这种调用。要用代码的规范来避免这种递归调用的发生。
"""
foo()
5>.递归总结
（1）递归是一种很自然的表达，符合逻辑思维
（2）递归相对运行效率低，每一次调用函数都要开辟栈帧
（3）递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了
（4）如果有限次数的递归，可以使用递归调用，或者使用循环代替，循环代码稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果
（5）绝大多数递归，都可以使用循环实现
（6）即使递归代码很简洁，但是能不用则不用递归
四.递归练习
1>.求N的阶乘
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comdef fac(n):
if n == 1:
return 1
return n * fac(n-1)N = 5print("{} 的阶乘为：{}".format(N,fac(N)))#以上代码执行结果如下:
5 的阶乘为：120
解法一（推荐使用这种方法，该函数性能最佳，因为时间复杂度是相同的，该解法最简单）
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comdef fac(n,p = 1):
if n == 1:
return p
p *= n
# print(p)
return fac(n - 1,p)N = 5print("{} 的阶乘为：{}".format(N,fac(N)))#以上代码执行结果如下:
5 的阶乘为：120
解法二
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comdef fac(n,p = None):
if p is None:
p = [1]
if n == 1:
return p[0] p[0] *= n
return fac(n - 1,p)N = 5print("{} 的阶乘为：{}".format(N,fac(N)))#以上代码执行结果如下:
5 的阶乘为：120
解法三
2>.将一个数逆序放入列表中，例如：1234=>【4,3,2,1】
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comdata = str(1234)def revert(x):
if x == -1:
return ""
return data[x] + revert(x -1)print(revert(len(data) - 1))#以上代码执行结果如下:
4321
解法一
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comdef revert(n,list_1 = None):
if list_1 is None:
list_1 = []
x,y = divmod(n,10)
list_1.append(y) if x == 0:
return list_1
return revert(x,list_1)print(revert(12345))#以上代码执行结果如下:
[5, 4, 3, 2, 1]
解法二
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comnum = 1234def revert(num,target=[]):
if num:
target.append(num[len(num) - 1]) #等效于target.append(num[-1:])
revert(num[:len(num) - 1])
return targetprint(revert(str(num)))#以上代码执行结果如下:
['', '', '', '']
解法三
3>.解决猴子吃桃问题
猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又吃了一个。第二天早上有将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第十天早上想吃时，只剩下一个桃子了。求第一天共摘了多少个桃子。
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comdef peach(days = 10):
if days == 1:
return 1
return (peach(days - 1) + 1) * 2print(peach())#以上代码执行结果如下:
1534
解法一
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.comdef peach(days = 1):
if days == 10:
return 1
return (peach(days + 1) + 1) * 2print("第一天共摘了{}个桃子".format(peach()))#以上代码执行结果如下:
第一天共摘了1534个桃子
解法二
4>.把字典扁平化
源字典 = {'a':{'b':,'c':}, 'd':{'e':,'f':{'g':}}}目标字典 = {'a.c':,'d.e':,'d.f.g':,'a.b':}
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.com source = {'a':{'b':1,'c':2},'d':{'e':3,'f':{'g':4}}} target = {} def flatmap(src,prefix=''):
for k,v in src.items():
if isinstance(v,(list,tuple,set,dict)):
flatmap(v,prefix=prefix + k + '.') #递归调用
else:
target[prefix + k] = v flatmap(source) print(target) #以上代码输出结果如下：
{'a.b': 1, 'a.c': 2, 'd.e': 3, 'd.f.g': 4}
解法一
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.com source = {'a':{'b':1,'c':2},'d':{'e':3,'f':{'g':4}}} def flatmap(src,dest=None,prefix=''):
if dest == None:
dest = {}
for k,v in src.items():
if isinstance(v,(list,tuple,set,dict)):
flatmap(v,dest,prefix=prefix + k + '.') #递归调用
else:
dest[prefix + k] = v return dest target = flatmap(source) print(target) #以上代码输出结果如下：
{'a.b': 1, 'a.c': 2, 'd.e': 3, 'd.f.g': 4}
解法二
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.com source = {'a':{'b':1,'c':2},'d':{'e':3,'f':{'g':4}}} def flatmap(src,dest=None,prefix=''):
def _flatmap(src,dest=None,prefix=''):
for k,v in src.items():
key = prefix + k
if isinstance(v,(list,tuple,set,dict)):
_flatmap(v,dest,key + ".") #递归调用
else:
dest[key] = v
dest = {}
_flatmap(src,dest)
return dest target = flatmap(source) print(target) #以上代码输出结果如下：
{'a.b': 1, 'a.c': 2, 'd.e': 3, 'd.f.g': 4}
解法三
5>.求2个字符串的最长公共子串
#！/usr/bin/env python
#_*_coding:utf-8_*_
#@author :yinzhengjie
#blog:http://www.cnblogs.com/yinzhengjie/tag/python%E8%87%AA%E5%8A%A8%E5%8C%96%E8%BF%90%E7%BB%B4%E4%B9%8B%E8%B7%AF/
#EMAIL:y1053419035@qq.com def findit(str1,str2):
count = 0
length = len(str1) for sublen in range(length,0,-1):
for start in range(0,length - sublen +1):
substr = str1[start:start + sublen]
count += 1
if str2.find(substr) > -1:
print("count={},substrlen={}0".format(count,sublen))
return substr s1 = "abcdefg"
s2 = "defabcdoabcdeftw"
s3 = "1234a" print(findit(s1,s2))
print(findit(s1,s3)) #以上代码输出结果如下:
count=2,substrlen=60
abcdef
count=22,substrlen=10
a
参考案例
