- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章浅谈Python 递归算法指归由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
1. 递归概述 。
递归( recursion)是一种编程技巧,某些情况下,甚至是无可替代的技巧。递归可以大幅简化代码,看起来非常简洁,但递归设计却非常抽象,不容易掌握。通常,我们都是自上而下的思考问题, 递归则是自下而上的解决问题——这就是递归看起来不够直观的原因。那么,究竟什么是递归呢?让我们先从生活中找一个栗子.
我们都有在黑暗的放映厅里找座位的经验:问问前排的朋友坐的是第几排,加上一,就是自己当前所处位置的排号。如果前排的朋友不知道自己是第几排,他可以用同样的方法得到自己的排号,然后再告诉你。如果前排的前排的朋友也不知道自己是第几排,他就如法炮制。这样的推导,不会无限制地进行下去,因为问到第一排的时候,坐在第一排的朋友一定会直接给出答案的。这就是递归算法在生活中的应用实例.
关于递归,不太严谨的定义是“一个函数在运行时直接或间接地调用了自身”。严谨一点的话,一个递归函数必须满足下面两个条件:
递归虽然晦涩,亦有规律可循。掌握了基本的递归理论,才有可能将其应用于复杂的算法设计中.
2. 线性递归 。
我们先从最经典的两个递归算法开始——阶乘(factorial)和斐波那契数列(Fibonacci sequence)。几乎所有讨论递归算法的话题,都是从从它们开始的。阶乘的概念比较简单,唯一需要说明的是,0的阶乘是1而非0。为此,我专门请教了我的女儿,她是数学专业的学生。斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列是这样定义的:
1
|
F(
0
)
=
1
,F(
1
)
=
1
, F(n)
=
F(n
-
1
)
+
F(n
-
2
)(n>
=
2
,n∈N,N为正整数集)
|
阶乘和斐波那契数列的递归算法如下:
1
2
3
4
5
6
7
8
9
|
def
factorial(n):
if
n
=
=
0
:
# 递归出口
return
1
return
n
*
factorial(n
-
1
)
# 向递归出口方向靠近的自身调用
def
fibonacci(n):
if
n <
2
:
# 递归出口
return
1
return
fibonacci(n
-
1
)
+
fibonacci(n
-
2
)
# 向递归出口方向靠近的自身调用
|
这两个函数的结构都非常简单,递归出口和自身调用清晰明了,但二者有一个显著的区别:阶乘函数中,只用一次自身调用,而斐波那契函数则有两次自身调用.
阶乘递归函数每一层的递归对自身的调用只有一次,因此每一层次上至多只有一个实例,且它们构成一个线性的次序关系。此类递归模式称作“线性递归”,这是递归最基本形式。非线性递归(比如斐波那契递归函数)在每一层上都会产生两个实例,时间复杂度为,极易导致堆栈溢出.
其实,用循环的方法同样可以简洁地写出上面两个函数。的确,很多情况下,递归能够解决的问题,循环也可以做到。但是,更多的情况下,循环是无法取代递归的。因此,深入研究递归理论是非常有必要的.
3. 尾递归 。
接下来,我们将上面的阶乘递归函数改造一下,仍然用递归的方式实现。为了便于比较,我们把两种算法放在一起.
1
2
3
4
5
6
7
8
9
10
11
|
def
factorial_A(n):
if
n
=
=
0
:
# 递归出口
return
1
return
n
*
factorial_A(n
-
1
)
# 向递归出口方向靠近的自身调用
def
factorial_B(n, k
=
1
):
if
n
=
=
0
:
# 递归出口
return
k
k
*
=
n
n
-
=
1
return
factorial_B(n,k)
# 向递归出口方向靠近的自身调用
|
比较 factorial_A() 和 factorial_B() 的写法,就会发现很有意思的问题。factorial_A() 的自身调用属于表达式的一部分,这意味着自身调用不是函数的最后一步,而是拿到自身调用的结果后,需要再做一次乘法运算;factorial_B() 的自身调用则是函数的最后一步。像 factorial_B() 函数这样,当自身调用是整个函数体中最后执行的语句,且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归(Tail Recursion)。尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码.
分别使用 factorial_A() 和 factorial_B() 计算5的阶乘,下图所示的计算过程,清晰展示了尾递归的优势:不用花费大量的栈空间来保存上次递归中的参数、局部变量等,这是因为上次递归操作结束后,已经将之前的数据计算出来,传递给当前的递归函数,这样上次递归中的局部变量和参数等就会被删除,释放空间,从而不会造成栈溢出.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
factorial_A(
5
)
5
*
factorial_A(
4
)
5
*
4
*
factorial_A(
3
)
5
*
4
*
3
*
factorial_A(
2
)
5
*
4
*
3
*
2
*
factorial_A(
1
)
5
*
4
*
3
*
2
*
1
*
factorial_A(
0
)
5
*
4
*
3
*
2
*
1
5
*
4
*
3
*
2
5
*
4
*
6
5
*
24
120
factorial_B(
5
, k
=
1
)
factorial_B(
4
, k
=
5
)
factorial_B(
3
, k
=
20
)
factorial_B(
2
, k
=
60
)
factorial_B(
1
, k
=
120
)
factorial_B(
0
, k
=
120
)
120
|
尾递归虽然有低耗高效的优势,但这一类递归一般都可转化为循环语句.
4. 单向递归 。
前文中两个递归函数,不管是阶乘还是斐波那契数列,递归总是向着递归出口方向进行,没有分支,没有反复,这样的递归,我们称之为单向递归。在文件递归遍历等应用场合,搜索完一个文件夹,通常要返回至父级目录,继续搜索其他兄弟文件夹,这个过程就不是单向的,而是有分叉的、带回溯的。通常复杂递归都不是单向的,算法设计起来就比较困难.
1
2
3
4
5
6
7
8
|
import
os
def
ergodic(folder):
for
root, dirs, files
in
os.walk(folder):
for
dir_name
in
dirs:
print
(os.path.join(root, dir_name))
for
file_name
in
files:
print
(os.path.join(root, file_name))
|
上面是借助于 os 模块的 walk() 实现的基于循环的文件遍历方法。虽然是循环结构,如果不熟悉 walk() 的话,这个函数看起来还是很不直观。我更喜欢下面的递归遍历方法.
1
2
3
4
5
6
7
8
|
import
os
def
ergodic(folder):
for
item
in
os.listdir(folder):
obj
=
os.path.join(folder, item)
print
(obj)
if
os.path.isdir(obj):
ergodic(obj)
|
5. 深度优先与广度优先 。
遍历文件通常有两种策略:深度优先搜索 DFS(depth-first search) 和广度优先搜索BFS(breadth-first search) 。顾名思义,深度优先就是优先处理本级文件夹中的子文件夹,递归向纵深发展;广度优先就是优先处理本级文件夹中的文件,递归向水平方向发展.
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
|
import
os
def
ergodic_DFS(folder):
"""基于深度优先的文件遍历"""
dirs, files
=
list
(),
list
()
for
item
in
os.listdir(folder):
if
os.path.isdir(os.path.join(folder, item)):
dirs.append(item)
else
:
files.append(item)
for
dir_name
in
dirs:
ergodic(os.path.join(folder, dir_name))
for
file_name
in
files
print
(os.path.join(folder, file_name))
def
ergodic_BFS(folder):
"""基于广度优先的文件遍历"""
dirs, files
=
list
(),
list
()
for
item
in
os.listdir(folder):
if
os.path.isdir(os.path.join(folder, item)):
dirs.append(item)
else
:
files.append(item)
for
file_name
in
files
print
(os.path.join(folder, file_name))
for
dir_name
in
dirs:
ergodic(os.path.join(folder, dir_name))
|
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我.
原文链接:https://blog.csdn.net/xufive/article/details/95971283 。
最后此篇关于浅谈Python 递归算法指归的文章就讲到这里了,如果你想了解更多关于浅谈Python 递归算法指归的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我是一名优秀的程序员,十分优秀!