递归虽然晦涩,亦有规律可循。掌握了基本的递归理论,才有可能将其应用于复杂的算法设计中。
我们先从最经典的两个递归算法开始——阶乘(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为正整数集)
阶乘和斐波那契数列的递归算法如下:
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) # 向递归出口方向靠近的自身调用
接下来,我们将上面的阶乘递归函数改造一下,仍然用递归的方式实现。为了便于比较,我们把两种算法放在一起。
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(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
尾递归虽然有低耗高效的优势,但这一类递归一般都可转化为循环语句。
前文中两个递归函数,不管是阶乘还是斐波那契数列,递归总是向着递归出口方向进行,没有分支,没有反复,这样的递归,我们称之为单向递归。在文件递归遍历等应用场合,搜索完一个文件夹,通常要返回至父级目录,继续搜索其他兄弟文件夹,这个过程就不是单向的,而是有分叉的、带回溯的。通常复杂递归都不是单向的,算法设计起来就比较困难。
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() 的话,这个函数看起来还是很不直观。我更喜欢下面的递归遍历方法。
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)
遍历文件通常有两种策略:深度优先搜索 DFS(depth-first search) 和广度优先搜索BFS(breadth-first search) 。顾名思义,深度优先就是优先处理本级文件夹中的子文件夹,递归向纵深发展;广度优先就是优先处理本级文件夹中的文件,递归向水平方向发展。
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))