博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
Python入门篇-递归函数Recursion
阅读量：7061 次
发布时间：2019-06-28

本文共 11711 字，大约阅读时间需要 39 分钟。

　　　　　　　　　　　　Python入门篇-递归函数（recursion）

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　作者：尹正杰

版权声明：原创作品，谢绝转载！否则将追究法律责任。

 

 

 

一.递归概述

　　（1）函数直接或者间接调用自身就是递归； 　　（2）递归需要有边界，递归前进段，递归返回段； 　　（3）递归一定要有边界条件； 　　（4）当边界条件不满足的时候，递归前进；　　 　　（5）当边界条件满足的时候，递归返回；

 

二.递归案例

1 #！/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #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/ 5 #EMAIL:y1053419035@qq.com 6  7 import sys 8  9 print("默认的递归调用次数限制0是：{} 次".format(sys.getrecursionlimit()))10 11 sys.setrecursionlimit(20000)    #我们修改默认的递归调用次数12 13 print("当前递归调用次数限制是：{} 次".format(sys.getrecursionlimit()))14 """15 递归要求：16     递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用。17     递归调用的深度不宜过深：18         Python对递归调用的深度做了限制，以保护解释器19         超过递归深度限制，抛出："RecursionError： maxinum recursion depth exceeded" 即超过了最大递归深度20         sys.getrecursionlimit()21 """22 23 24 25 """26     斐波拉契数字推理公式：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)27 """28 def fib(n):29     return 1 if n < 2 else fib(n-1) + fib(n-2)30 31 for i in range(20):32     print(fib(i), end=' ')33 34 35 #以上代码执行结果如下:36 默认的递归调用次数限制0是：1000 次37 当前递归调用次数限制是：20000 次38 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

 

三.递归的性能

1>.使用for循环打印斐波拉契前35个数字

1 #！/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #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/ 5 #EMAIL:y1053419035@qq.com 6  7  8 import datetime 9 10 start = datetime.datetime.now()11 12 pre = 013 14 cur = 1 # No115 16 print(pre, cur, end=' ')17 18 n = 3519 20 for i in range(n-1):21     pre, cur = cur, pre + cur22     print(cur, end=' ')23 24 delta = (datetime.datetime.now() - start).total_seconds()25 26 print("\n递归调用打印斐波拉契钱35个数字的时间为：{}".format(delta))27 28 29 30 #以上代码直接结果如下:31 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 32 递归调用打印斐波拉契钱35个数字的时间为：0.0

2>.使用递归方式打印斐波拉契前35个数字

1 #！/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #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/ 5 #EMAIL:y1053419035@qq.com 6  7 import datetime 8  9 n = 3510 11 start = datetime.datetime.now()12 13 def fib(n):14     return 1 if n < 2 else fib(n-1) + fib(n-2)15 16 for i in range(n):17     print(fib(i), end=' ')18 19 delta = (datetime.datetime.now() -start).total_seconds()20 21 print("\n递归调用打印斐波拉契钱35个数字的时间为：{}".format(delta))22 23 24 25 #以上代码直接结果如下:26 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 27 递归调用打印斐波拉契钱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)))#以上代码执行结果如下:['4', '3', '2', '1']
解法三

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':1,'c':2}, 'd':{
   'e':3,'f':{
   'g':4}}}目标字典 = {
   'a.c':2,'d.e':3,'d.f.g':4,'a.b':1}
1 #！/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #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/ 5 #EMAIL:y1053419035@qq.com 6  7  8 source = {
    'a':{
    'b':1,'c':2},'d':{
    'e':3,'f':{
    'g':4}}} 9 10 target = {}11 12 13 def flatmap(src,prefix=''):14     for k,v in src.items():15         if isinstance(v,(list,tuple,set,dict)):16             flatmap(v,prefix=prefix + k + '.')      #递归调用17         else:18             target[prefix + k] = v19 20 flatmap(source)21 22 print(target)23 24 25 26 #以上代码输出结果如下：27 {
    'a.b': 1, 'a.c': 2, 'd.e': 3, 'd.f.g': 4}
解法一 
1 #！/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #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/ 5 #EMAIL:y1053419035@qq.com 6  7  8 source = {
    'a':{
    'b':1,'c':2},'d':{
    'e':3,'f':{
    'g':4}}} 9 10 11 def flatmap(src,dest=None,prefix=''):12     if dest == None:13         dest = {}14     for k,v in src.items():15         if isinstance(v,(list,tuple,set,dict)):16             flatmap(v,dest,prefix=prefix + k + '.')      #递归调用17         else:18             dest[prefix + k] = v19 20     return dest21 22 target = flatmap(source)23 24 print(target)25 26 27 28 #以上代码输出结果如下：29 {
    'a.b': 1, 'a.c': 2, 'd.e': 3, 'd.f.g': 4}
解法二 
1 #！/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #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/ 5 #EMAIL:y1053419035@qq.com 6  7  8 source = {
    'a':{
    'b':1,'c':2},'d':{
    'e':3,'f':{
    'g':4}}} 9 10 11 def flatmap(src,dest=None,prefix=''):12     def _flatmap(src,dest=None,prefix=''):13         for k,v in src.items():14             key = prefix + k15             if isinstance(v,(list,tuple,set,dict)):16                 _flatmap(v,dest,key + ".")              #递归调用17             else:18                 dest[key] = v19     dest = {}20     _flatmap(src,dest)21     return dest22 23 target = flatmap(source)24 25 print(target)26 27 28 29 #以上代码输出结果如下：30 {
    'a.b': 1, 'a.c': 2, 'd.e': 3, 'd.f.g': 4}
解法三

5>.实现Base64编码（要求自己实现算法，不用库）

索引
对应字符
索引
对应字符
索引
对应字符
索引
对应字符
0
A
17
R
34
i
51
z
1
B
18
S
35
j
52
0
2
C
19
T
36
k
53
1
3
D
20
U
37
l
54
2
4
E
21
V
38
m
55
3
5
F
22
W
39
n
56
4
6
G
23
X
40
o
57
5
7
H
24
Y
41
p
58
6
8
I
25
Z
42
q
59
7
9
J
26
a
43
r
60
8
10
K
27
b
44
s
61
9
11
L
28
c
45
t
62
+
12
M
29
d
46
u
63
/
13
N
30
e
47
v
   
14
O
31
f
48
w
   
15
P
32
g
49
x
   
16
Q
33
h
50
y

 

 

1 #！/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #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/ 5 #EMAIL:y1053419035@qq.com 6  7  8 import  base64 9 10 s1 = "abcdfg"11 12 print(base64.b64encode(s1.encode()))13 14 15 #以上代码输出结果如下:16 b'YWJjZGZn'
使用base64代码实现方式 

6>.求2个字符串的最长公共子串

1 #！/usr/bin/env python 2 #_*_coding:utf-8_*_ 3 #@author :yinzhengjie 4 #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/ 5 #EMAIL:y1053419035@qq.com 6  7  8 def findit(str1,str2): 9     count = 010     length = len(str1)11 12     for sublen in range(length,0,-1):13         for start in range(0,length - sublen +1):14             substr = str1[start:start + sublen]15             count += 116             if str2.find(substr) > -1:17                 print("count={},substrlen={}0".format(count,sublen))18                 return substr19 20 s1 = "abcdefg"21 s2 = "defabcdoabcdeftw"22 s3 = "1234a"23 24 print(findit(s1,s2))25 print(findit(s1,s3))26 27 28 29 #以上代码输出结果如下:30 count=2,substrlen=6031 abcdef32 count=22,substrlen=1033 a
参考案例

 

转载于:https://www.cnblogs.com/yinzhengjie/p/10961457.html

你可能感兴趣的文章
《谁动了我的奶酪》--[美]斯宾塞·约翰逊
查看>>
【Android】Eclipse性能优化，快捷方式，文档注释
查看>>
$('#checkbox').attr('checked'); 返回的是checked或者是undefined解决办法
查看>>
Hyper-V 替换 vmwp
查看>>
永远先做最重要的事
查看>>
TinyFrame升级之二：数据底层访问部分
查看>>
关于LINQ和SQL操作数据库的性能测试（转)
查看>>
SqlServer性能检测和优化工具使用详细
查看>>
(转)C#与Outlook交互收发邮件
查看>>
GObject对象系统
查看>>
如何将松散的dll打包进需要发布的exe
查看>>
刘兰芝_百度百科
查看>>
C/C++产生随机数
查看>>
Android ProgressBar的使用
查看>>
jquery 新建的元素事件绑定问题
查看>>
最新版的Android4.4.2 SDK无法下载解决
查看>>
c fopen
查看>>
Linux 小知识翻译 - 「Linux」和「发行版」之间的关系
查看>>
FBX导入错误 ：ImportFBX Errors:
查看>>
《设计模式》工厂家族
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-02-07 15:18:10   当前IP: 18.222.140.99   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我