1. 递归概述

递归（ recursion）这是一种编程技能，在某些情况下，甚至是不可替代的技能。递归可以极大地简化代码，看起来非常简单，但递归设计非常抽象，不容易掌握。通常，我们从上到下思考， 递归是自下而上的问题——这就是递归看起来不够直观的原因。那么，递归到底是什么呢？让我们从生活中找到栗子。

我们都有在黑暗的放映厅找座位的经验：问前排的朋友坐在第一排，加上一个，是他们目前的位置。如果前排的朋友不知道他是什么排，他可以用同样的方法得到他的排名，然后告诉你。如果前排的朋友不知道他是什么排，他就会这样做。这样的推导，不会系统地继续下去，因为当被问及第一排时，坐在第一排的朋友会直接给出答案。这就是递归算法在生活中的应用实例。

至于递归，不太严格的定义是“一个函数在运行过程中直接或间接调用自己”。如果更严格，递归函数必须满足以下两个条件：

(1)至少有一个明确的递归结束条件，我们称之为递归出口，有些人喜欢称之为递归基。

(2)直接或间接地调用自己，接近递归出口方向(也称递归调用)。

虽然递归晦涩难懂，但也有规律可循。只有掌握了基本的递归理论，才能将其应用到复杂的算法设计中。

2. 线性递归

让我们从最经典的两种递归算法开始-阶乘（factorial）以及斐波那契数列（Fibonacci sequence）。几乎所有讨论递归算法的话题都是从它们开始的。阶级的概念相对简单。唯一需要解释的是，0的阶级是1而不是0。为此，我特别问了我的女儿，她是一名数学专业的学生。斐波那契数列，又称黄金分割数列，是指这样一个数列：1、1、2、3、5、8、13、21、34、...斐波纳契数列在数学上是这样定义的:

F(0)=1，F(1)=1,F(n)=F(n-1)+F(n-2)（n>=2，n∈N，N为正整数集)

阶乘和斐波那契数列的递归算法如下：

deffactorial(n):
ifn==0:#递归出口
return1
returnn*factorial(n-1)#接近递归出口方向的自我调用
deffibonacci(n):
ifn<2:#递归出口
return1
returnfibonacci(n-1)+fibonacci(n-2)#接近递归出口方向的自我调用

这两个函数的结构都很简单，递归出口和自身调用都很清楚，但是两者有一个明显的区别:阶乘函数只调用一次，而斐波那契函数调用两次。

阶级递归函数每层的递归只调用一次，所以每层最多只有一个例子，它们构成一个线性顺序关系。这种递归模式被称为“线性递归”，这是递归最基本的形式。非线性递归（如斐波那契递归函数）在每层产生两个例子，时间复杂性为

，容易导致堆栈溢出。

事实上，上述两个函数也可以通过循环简单地写出来。事实上，在许多情况下，递归可以解决问题，循环也可以实现。然而，在更多的情况下，循环并不能取代递归。因此，有必要深入研究递归理论。

3. 尾递归

接下来，我们将以上阶乘递归函数进行改造，仍然以递归的方式实现。为了便于比较，我们将两种算法放在一起。

deffactorial_A(n):
ifn==0:#递归出口
return1
returnn*factorial_A(n-1)#接近递归出口方向的自我调用
deffactorial_B(n,k=1):
ifn==0:#递归出口
returnk
k*=n
n-=1
returnfactorial_B(n,k)#接近递归出口方向的自我调用

比较 factorial_A() 和 factorial_B() 写作，会发现很有趣的问题。factorial_A() 自我调用是表达式的一部分，这意味着自我调用不是函数的最后一步，而是需要在获得自我调用结果后再次乘法；factorial_B() 函数的最后一步是自我调用。就像 factorial_B() 函数是这样的，当自我调用是整个函数体中最终执行的句子，其返回值不是表达式的一部分时，这种递归调用是尾递归（Tail Recursion）。尾递归函数的特点是在回归过程中不需要任何操作，因为大多数现代编译器会利用这一特点自动生成优化代码。

分别使用 factorial_A() 和 factorial_B() 计算5的阶乘性，如下图所示的计算过程，清楚地显示了尾递归的优点：不需要花费大量的堆栈空间来保存上次递归的参数、局部变量等，这是因为上次递归操作后，计算了以前的数据，并将其传递给当前的递归函数，因此上次递归的局部变量和参数将被删除并释放空间，以免造成堆栈溢出。

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. 单向递归

在上述两个递归函数中，无论是阶级还是斐波那契数列，递归总是朝着递归出口的方向进行，没有分支，没有重复，这种递归，我们称之为单向递归。在文件递归遍历和其他应用程序中，搜索文件夹后，通常返回到父级目录，继续搜索其他兄弟文件夹。这个过程不是单向的，而是分叉的和可追溯的。通常，复杂的递归不是单向的，算法很难设计。

importos
defergodic(folder):
forroot,dirs,filesinos.walk(folder):
fordir_nameindirs:
print(os.path.join(root,dir_name))
forfile_nameinfiles:
print(os.path.join(root,file_name))

以上是借助 os 模块的 walk() 实现基于循环的文件遍历法。虽然是循环结构，但如果不熟悉 walk() 这个函数看起来还是很不直观的。我更喜欢以下递归遍历方法。

importos
defergodic(folder):
foriteminos.listdir(folder):
obj=os.path.join(folder,item)
print(obj)
ifos.path.isdir(obj):
ergodic(obj)

5. 深度优先，广度优先

通常有两种策略：深度优先搜索 DFS（depth-first search） 优先搜索BFS和广度（breadth-first search） 。顾名思义，深度优先是对同级文件夹中的子文件夹进行优先处理，递归向深度发展；广度优先是优先处理同级文件夹中的文件，递归向水平方向发展。

importos
defergodic_DFS(folder):
"""基于深度优先级的文件遍历"""
dirs,files=list(),list()
foriteminos.listdir(folder):
ifos.path.isdir(os.path.join(folder,item)):
dirs.append(item)
else:
files.append(item)
fordir_nameindirs:
ergodic(os.path.join(folder,dir_name))
forfile_nameinfiles
print(os.path.join(folder,file_name))
defergodic_BFS(folder):
"""基于广度优先级的文件遍历"""
dirs,files=list(),list()
foriteminos.listdir(folder):
ifos.path.isdir(os.path.join(folder,item)):
dirs.append(item)
else:
files.append(item)
forfile_nameinfiles
print(os.path.join(folder,file_name))
fordir_nameindirs:
ergodic(os.path.join(folder,dir_name))

python学习网络，免费在线学习python平台，欢迎关注！