递归算法

2.1 文件树遍历

来看看用于遍历文件树的递归算法。算法将遍历目录及其所有子目录，打印出所有文件和文件夹的列表。

import os

def list_files_recursive(directory, indent=0):
    # 获取当前目录中的所有文件和文件夹列表
    items = os.listdir(directory)
                
    for item in items:
        # 创建文件或文件夹的完整路径
        path = os.path.join(directory, item)
                    
        # 使用缩进打印以更好地感知结构
        print(' ' * indent + item)
                    
        # 如果是文件夹，递归遍历其内容
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# 使用示例
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

这如何工作？

1. 函数 list_files_recursive(directory, indent=0):
   • directory — 当前目录，我们要打印其内容。
   • indent — 当前的缩进级别，用于显示文件和文件夹的嵌套关系。
2. 获取当前目录中的所有文件和文件夹列表 使用 os.listdir(directory).
3. 遍历列表中的每个元素 items.
4. 创建元素的完整路径 使用 os.path.join(directory, item).
5. 打印元素名称 使用缩进，每个嵌套级别增加4个空格。
6. 检查元素是否为文件夹 使用 os.path.isdir(path). 如果是，递归调用 list_files_recursive(path, indent + 4) 遍历其内容。

输出示例：

假设我们有以下目录结构：

root_directory/
    file1.txt
    dir1/
        file2.txt
        file3.txt
        dir2/
            file4.txt
    file5.txt

执行函数 list_files_recursive(root_directory) 我们将得到以下输出：

file1.txt
dir1
    file2.txt
    file3.txt
    dir2
        file4.txt
file5.txt

这个算法递归地遍历目录树，打印出所有文件和文件夹，显示其嵌套关系。

2.2 汉诺塔

汉诺塔问题

汉诺塔是一个经典的递归问题，涉及将圆盘从一个柱子移到另一个柱子，使用辅助柱。

规则：

1. 每次只能移动一个盘子。
2. 盘子只能放在空柱子上或者更大的盘子上。
3. 需要将所有盘子从一个柱子移到另一个柱子，使用辅助柱。

以下是解决这个问题的递归算法：

汉诺塔算法解决问题的方法如下：

1. 使用目标柱，将n - 1个盘子从起始柱移到辅助柱。
2. 将剩下的盘子从起始柱移到目标柱。
3. 使用起始柱，将n - 1个盘子从辅助柱移到目标柱。

Python示例

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"移动盘子1从{source}到{target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"移动盘子{n}从{source}到{target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# 使用示例：
n = 3  # 盘子数量
hanoi_tower(n, 'A', 'C', 'B')
        

这如何工作？

基本情况：

如果只有一个盘子(n == 1)，则可以直接从起始柱移到目标柱。

if n == 1:
    print(f"移动盘子1从{source}到{target}")
    return

递归情况：

步骤1. 使用目标柱，将n-1盘子从起始柱移到辅助柱。

hanoi_tower(n - 1, source, auxiliary, target)

步骤2. 将盘子n从起始柱移到目标柱。

print(f"移动盘子{n}从{source}到{target}")

步骤3. 使用起始柱，将n - 1盘子从辅助柱移到目标柱。

hanoi_tower(n - 1, auxiliary, target, source)

输出示例：

对于三盘子(n = 3)在柱子A, B和C，程序输出：

移动盘子1从A到C
移动盘子2从A到B
移动盘子1从C到B
移动盘子3从A到C
移动盘子1从B到A
移动盘子2从B到C
移动盘子1从A到C

2.3 科赫雪花

使用递归绘制雪花是一个有趣的问题，常用于研究分形。绘制雪花的简单方法之一是使用科赫曲线，这是一种分形曲线。

绘制科赫雪花的算法

科赫曲线构建如下：

• 从一条直线开始。
• 将每个线段分成三部分，用一个小的曲线替代中间部分，像一个“角”。
• 递归地对每个线段重复这个过程。

分步指南

• 开始：画初始线段。
• 分裂：将每个线段分成三部分。
• 替换中间部分：在中间部分画一个“角”，由两条线构成，形成60度角。
• 重复过程：对每个线段继续这个过程。

使用Turtle库的Python示例

import turtle

def draw_koch_curve(t, length, depth):
    if depth == 0:
        t.forward(length)
    else:
        length /= 3.0
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
        t.right(120)
        draw_koch_curve(t, length, depth - 1)
        t.left(60)
        draw_koch_curve(t, length, depth - 1)
            
def draw_snowflake(t, length, depth):
    for _ in range(3):
        draw_koch_curve(t, length, depth)
        t.right(120)
            
# 设置屏幕
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# 设置乌龟
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# 画雪花
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# 完成绘图
turtle.done()
            

这如何工作？

1. 函数 draw_koch_curve(t, length, depth):

• t: 绘图的乌龟。
• length: 线段的长度。
• depth: 递归深度，定义细节的层次。

2. 基本情况：

如果depth等于0，乌龟画一条直线。

if depth == 0:
    t.forward(length)
        

3. 递归情况：

将线段分为三部分，并递归地对每部分应用draw_koch_curve，加入转向。

length /= 3.0
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)
t.right(120)
draw_koch_curve(t, length, depth - 1)
t.left(60)
draw_koch_curve(t, length, depth - 1)

4. 函数 draw_snowflake(t, length, depth):

画出三条科赫曲线，连接成一个雪花形。

for _ in range(3):
    draw_koch_curve(t, length, depth)
    t.right(120)

如何运行代码？

• 确保你安装了Turtle库 (pip install PythonTurtle)。
• 复制并粘贴代码到.py文件并运行。你将在屏幕上看到画雪花。

这个算法允许使用简单的递归和几何建模可视化雪花的分形结构。