脚本之家，脚本语言编程技术及教程分享平台！
分类导航

Python|VBS|Ruby|Lua|perl|VBA|Golang|PowerShell|Erlang|autoit|Dos|bat|

服务器之家 - 脚本之家 - Python - Python全栈之递归函数

Python全栈之递归函数

2022-03-10 13:12熬夜泡枸杞 Python

这篇文章主要为大家介绍了Python递归函数，具有一定的参考价值，感兴趣的小伙伴们可以参考一下，希望能够给你带来帮助

1. 递归函数

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# ### 递归函数
"""
递归函数 : 自己调用自己的函数 , 叫做递归函数
递 : 去
归 : 回
一去一回叫做递归
"""
def digui(n):
    print(n,"<==1==>")
    if n > 0:
        digui(n-1)
    print(n,"<==2==>")
digui(5)
"""
# 去的过程
n = 5 print(5,"<==1==>")  if 5 > 0:   digui(5-1) =>  digui(4) 代码阻塞在第12行
n = 4 print(4,"<==1==>")  if 4 > 0:   digui(4-1) =>  digui(3) 代码阻塞在第12行
n = 3 print(3,"<==1==>")  if 3 > 0:   digui(3-1) =>  digui(2) 代码阻塞在第12行
n = 2 print(2,"<==1==>")  if 2 > 0:   digui(2-1) =>  digui(1) 代码阻塞在第12行
n = 1 print(1,"<==1==>")  if 1 > 0:   digui(1-1) =>  digui(0) 代码阻塞在第12行
n = 0 print(0,"<==1==>")  if 0 > 0: 不成立 print(0,"<==2==>") 到此最后一层函数空间彻底执行完毕
# 回的过程
回到上一层函数空间  n = 1 代码在第12行的位置,继续往下执行  print(1,"<==2==>")
回到上一层函数空间  n = 2 代码在第12行的位置,继续往下执行  print(2,"<==2==>")
回到上一层函数空间  n = 3 代码在第12行的位置,继续往下执行  print(3,"<==2==>")
回到上一层函数空间  n = 4 代码在第12行的位置,继续往下执行  print(4,"<==2==>")
回到上一层函数空间  n = 5 代码在第12行的位置,继续往下执行  print(5,"<==2==>")
到此递归函数执行结束..
打印 543210012345
"""
"""
每次调用函数时,都要单独在内存当中开辟空间,叫做栈帧空间,以运行函数中的代码
递归总结:
    (1)递归实际上是不停的开辟栈帧空间和释放栈帧空间的过程,开辟就是去的过程,释放就是回的过程
    (2)递归什么时候触发归的过程:
        1.当最后一层栈帧空间执行结束的时候,触发归的过程.
        2.当遇到return返回值的时候终止当前函数,触发归的过程.
    (3)递归不能无限的去开辟空间,可能造成内存溢出,蓝屏死机的情况,所以一定要给予跳出的条件(如果递归的层数太大,不推荐使用)
    (4)开辟的一个个栈帧空间,数据是彼此独立不共享的.
"""
# 递归不能不限开辟空间
"""官方说法最大默认是1000层."""
def deepfunc():
    deepfunc()
deepfunc()

Python全栈之递归函数

Python全栈之递归函数

Python全栈之递归函数

2. 递归练习

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
# ### 1.使用递归实现任意数n的阶乘
# 普通实现
# 5! =5 *4*3*2*1
n = 5
total = 1
for i in range(n,0,-1):
    total *= i
print(total) # 120
# 递归实现
def jiecheng(n):
    if n <= 1:
        return 1
    return jiecheng(n-1) * n
print(jiecheng(2))
# jiecheng(1) => 1
# jiecheng(2) => jiecheng(1) * 2 => 1 * 2
# jiecheng(3) => jiecheng(2) * 3 => 1 * 2 * 3
# jiecheng(4) => jiecheng(3) * 4 => 1 * 2 * 3 * 4
# jiecheng(5) => jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5
print(jiecheng(5))
"""
代码解析:
去的过程:
n = 5 return jiecheng(n-1) * n => jiecheng(4) * 5
n = 4 return jiecheng(n-1) * n => jiecheng(3) * 4
n = 3 return jiecheng(n-1) * n => jiecheng(2) * 3
n = 2 return jiecheng(n-1) * n => jiecheng(1) * 2
n = 1 return 1
回的过程:
n = 2 return jiecheng(1) * 2 => 1 * 2
n = 3 return jiecheng(2) * 3 => 1 * 2 * 3
n = 4 return jiecheng(3) * 4 => 1 * 2 * 3 * 4
n = 5 return jiecheng(4) * 5 => 1 * 2 * 3 * 4 * 5
到此程序结束:
返回  1 * 2 * 3 * 4 * 5
"""
print("<====================>")
# ### 2. 使用尾递归来实现任意数的阶乘
""" return 在哪调用,在哪返回 """
"""自己调用自己,且返回时非运算表达式,只是函数本身"""
"""
特点:
    尾递归只开辟一个空间,不会无限的开辟,在一个空间里面去计算最后的结果进行返回,比较节省空间,有的解释器支持尾递归的调用特点
    但是cpython解释器目前不支持
写法:
    所有运算的值都在函数的参数中计算完毕,最后返回运算的参数;
"""
def jiecheng(n,endval):
    if n <= 1:
        return endval
    return jiecheng(n-1 , n * endval)
res = jiecheng(5,1) # 5*4*3*2*1
print(res)
"""
代码解析:
去的过程
n = 5 ,endval = 1 return jiecheng(n-1 , n * endval) => jiecheng(4,5*1) => 5*1*4*3*2
n = 4 ,endval = 5*1 return jiecheng(n-1 , n * endval) => jiecheng(3,5*1*4) => 5*1*4*3*2
n = 3 ,endval = 5*1*4 return jiecheng(n-1 , n * endval) => jiecheng(2,5*1*4*3) => 5*1*4*3*2
n = 2 ,endval = 5*1*4*3 return jiecheng(n-1 , n * endval) => jiecheng(1,5*1*4*3*2) => 5*1*4*3*2
n = 1 ,endval = 5*1*4*3*2   if n <= 1 成立  return endval
endval = 5*1*4*3*2
最下层空间的返回值 是 5*4*3*2*1  最上层接收到的返回值也是 5*4*3*2*1
最下层和最上层返回的结果是一致的,所以对于尾递归来说,只需要考虑去的过程,无需考虑回的过程即可完成;
"""
# 优化代码1
def jiecheng(n,endval=1):
    if n <= 1:
        return endval
    return jiecheng(n-1 , n * endval)
res = jiecheng(5,100) # 5*4*3*2*1
print(res,"<00000>")
# 优化代码2 [把尾递归需要的参数值隐藏起来,避免篡改.]
def outer(n):
    def jiecheng(n,endval=1):
        if n <= 1:
            return endval
        return jiecheng(n-1 , n * endval)
    return jiecheng(n,1)# 120
print(outer(5))
# 优化代码3(扩展)
# 闭包实现
def outer(n):
    endval = 1
    def jiecheng(n):
        nonlocal endval
        if n <= 1:
            return endval
        endval *= n
        return jiecheng(n-1)
    return jiecheng
func = outer(5)
print(func(5),"<===111==>")
print("<================>")
# ### 3.使用递归来完成斐波那契数列
""" 1 1 2 3 5 8 13 21 34 ... """
def feib(n):
    if n == 1 or n == 2:
        return 1
    # 上一个结果 + 上上个结果
    return feib(n-1) + feib(n-2)
print(feib(5))
"""
# 代码解析:
n = 5               feib(5) => 3 + 2 => return 5 
        feib(4)        +         feib(3)
    feib(3)+feib(2)          feib(2)+feib(1) => 1 + 1 => 2
feib(2)+feib(1)+feib(2) => 1 + 1 + 1 => 3   
"""

Python全栈之递归函数

3. 小练习

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
# (选做)
# 1.可滑动的序列 自定义一个函数 根据参数n的值 , 变成对应个元素的容器 （zip）
"""
listvar = [1,2,3,4,5,6,7,8,9]
n = 2
listvar = [[1,2],[3,4],[5,6],[7,8]]
n = 3
listvar = [[1,2,3],[4,5,6],[7,8,9]]
n = 4
listvar = [[1,2,3,4],[5,6,7,8]]
"""
"""
lst1 = [1,3,5,7,9]
lst2 = [2,4,6,8]
zip(lst1,lst2)
"""
listvar = [1,2,3,4,5,6,7,8,9]
n = 2
lst1 = [1,3,5,7,9]
lst2 = [2,4,6,8]
# lst1 = listvar[0::2]  <=> [1,3,5,7,9]
# lst2 = listvar[1::2]  <=> [2,4,6,8]
print(lst2,"1111")
print(list( zip(lst1,lst2) ))
n = 3
lst1 = [1,4,7]
lst2 = [2,5,8]
lst3 = [3,6,9]
# lst1 = listvar[0::3]  <=> [1,4,7]
# lst2 = listvar[1::3]  <=> [2,5,8]
# lst3 = listvar[2::3]  <=> [3,6,9]
print(lst1,"2222")
print(list( zip(lst1,lst2,lst3) ))
n = 4
lst1 = [1,5]
lst2 = [2,6]
lst3 = [3,7]
lst4 = [4,8]
# lst1 = listvar[0::4]  <=> [1,5,9]
# lst2 = listvar[1::4]  <=> [2,6]
# lst3 = listvar[2::4]  <=> [3,7]
# lst4 = listvar[3::4]  <=> [4,8]
print(lst1,"3333")
print(list( zip(lst1,lst2,lst3,lst4) ))
print("<=============>")
n = 3
lst = [ listvar[i::n] for i in range(n) ]
print(lst) # [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
# zip(*lst) => zip([1,4,7],[2,5,8],[3,6,9])
it = zip(*lst)
print(list(it))
func = lambda n : zip(  *[ listvar[i::n] for i in range(n) ]   )
it = func(2)
# 把里面的元组强转成列表
print(list(map(list,it)))
# 2.青蛙跳台阶  (递归实现)
'''
一只青蛙要跳上n层高的台阶
一次能跳一级,也可以跳两级
请问这只青蛙有多少种跳上这个n层高台阶的方法?
n = 1   1 => 1
n = 2   2 => 1 1 | 2
n = 3   3 => 1 1 1 | 1 2 | 2 1
n = 4   5 => 1 1 1 1 | 1 2 1 | 2 1 1 | 1 1 2 | 2 2
n = 5   8 => 1 1 1 1 1 | 1 1 1 2 |2 1 1 1 | 1 2 1 1  | 1 1 2 1 | 2 2 1 | 1 2 2 | 2 1 2
'''
def func(n):
    if n == 1 or n == 2:
        return n
    return func(n-1) + func(n-2)
print(func(5))
# 3.递归反转字符串 "将14235 反转成53241" (递归实现)
# 把后面的字符往前挪动 方法一
strvar = "14235"
# lst.append(5)
# lst.append(3)
# lst.append(2)
# lst.append(4)
# lst.append(1)
# lth = 字符串的总长度  lst 要插入的列表
def func(lth,lst=[]):
    if lth == 0:
        return lst
    res = strvar[lth-1]
    lst.append(res)
    return func(lth-1)
lth = len(strvar)
lst = func(lth)
print(lst) # ['5', '3', '2', '4', '1']
print("".join(lst))
# 简写
def func(lth,lst=[]):
    if lth == 0:
        return "".join(lst)
    res = strvar[lth-1]
    lst.append(res)
    return func(lth-1)
print(func(lth))
# 把前面的字符往后挪动 方法二
strvar = "14235"
def func(strvar):
    if len(strvar) == 1:
        return strvar
    return func(strvar[1:])+strvar[0]
res = func(strvar)
print(res)
"""
递:
return func(4235) + 1
return func(235)  + 4
return func(35)   + 2
return func(5)    + 3
return 5
归:
return func(5)    + 3 => 5 + 3
return func(35)   + 2 => 5 + 3 + 2
return func(235)  + 4 => 5 + 3 + 2 + 4
return func(4235) + 1 => 5 + 3 + 2 + 4 + 1
return 5 + 3 + 2 + 4 + 1
"""
 
# 4.斐波那契数列用尾递归实现
a,b = 0,1
i = 0
n = 5
while i < n:
    print(b)
    a,b = b,a+b
    i +=1
a,b = 0,1
n = 5
while n > 0:
    print(b)
    a,b = b,a+b
    n -= 1
print("<==============>")
def func(n,a=0,b=1):
    if n == 1:
        return b
    return func(n-1,b,a+b)
print(func(6))

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注服务器之家的更多内容!

原文链接：https://blog.csdn.net/weixin_46818279/article/details/121186680

  • Python
  • 递归函数

    • 延伸 · 阅读

    精彩推荐
    最近更新
    编辑推荐
    阅读排行
    热门标签
    2048 　 6006 　 contextlib 　 SLOTS 　 MELIAE 　 FEEDPARSER 　 暂存 　 持久性管理 　 pickle模块 　 THREADING 　 reduce 　 nignx 　 装饰器 　 函数式编程 　 兔子毒药 　 监控文件 　 流量监控 　 Web框架 　 办公工具 　 PIL库 　 高斯模糊 　 wxPython 　 import 　 自定义模块 　 Python开发 　 元类 　 metaclass 　 魔术方法 　 DNSPod 　 动态解析域名 　
    © 2019-2023 脚本之家 | 服务器之家(www.zzvips.com)旗下站点 版权所有关于我们联系我们版权申明网站地图