遞迴演算法

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度角的線段構成。
• 重複過程：對每個線段繼續此過程。

使用 Python 和 Turtle 圖書館的範例

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文件並運行它。你會看到螢幕上繪製雪花。

此算法允許使用簡單的遞迴和幾何構建原則來視覺化雪花的分形結構。