Thuật toán đệ quy

2.1 Duyệt cây thư mục

Hãy cùng xem xét một thuật toán đệ quy để duyệt cây thư mục. Thuật toán sẽ duyệt qua thư mục và tất cả các thư mục con của nó, hiển thị danh sách tất cả các tệp và thư mục.

import os

def list_files_recursive(directory, indent=0):
    # Lấy danh sách tất cả các tệp và thư mục trong thư mục hiện tại
    items = os.listdir(directory)
                
    for item in items:
        # Tạo đường dẫn đầy đủ đến tệp hoặc thư mục
        path = os.path.join(directory, item)
                    
        # Hiển thị với khoảng cách để dễ dàng xem cấu trúc hơn
        print(' ' * indent + item)
                    
        # Nếu đây là một thư mục, duyệt nội dung của nó đệ quy
        if os.path.isdir(path):
            list_files_recursive(path, indent + 4)
            
# Ví dụ sử dụng
root_directory = '/path/to/root/directory'
list_files_recursive(root_directory)

Nó hoạt động như thế nào?

1. Hàm list_files_recursive(directory, indent=0):
   • directory — thư mục hiện tại mà chúng ta muốn hiển thị.
   • indent — mức độ thụt lề hiện tại để hiển thị độ sâu của các tệp và thư mục.
2. Lấy danh sách tất cả các tệp và thư mục trong thư mục hiện tại bằng cách sử dụng os.listdir(directory).
3. Duyệt qua từng mục trong danh sách items.
4. Tạo đường dẫn đầy đủ đến mục đó bằng cách sử dụng os.path.join(directory, item).
5. Hiển thị tên mục với mức độ thụt lề, tăng thêm 4 khoảng trắng cho mỗi mức độ lồng nhau.
6. Kiểm tra xem mục có phải là thư mục bằng os.path.isdir(path). Nếu đúng, gọi đệ quy list_files_recursive(path, indent + 4) để duyệt nội dung của nó.

Ví dụ đầu ra:

Giả sử chúng ta có cấu trúc thư mục sau:

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

Khi thực thi hàm list_files_recursive(root_directory) chúng ta sẽ nhận được đầu ra như sau:

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

Thuật toán này duyệt đệ quy cây thư mục, hiển thị tất cả các tệp và thư mục theo độ sâu lồng nhau.

2.2 Tháp Hà Nội

Bài toán "Tháp Hà Nội"

Tháp Hà Nội là một bài toán cổ điển về đệ quy, liên quan đến việc di chuyển các đĩa từ cọc này qua cọc khác bằng cách sử dụng cọc phụ trợ.

Quy tắc:

1. Chỉ có thể di chuyển một đĩa mỗi lần.
2. Đĩa chỉ có thể được đặt trên cọc trống hoặc trên đĩa có kích thước lớn hơn.
3. Cần di chuyển tất cả các đĩa từ cọc này qua cọc khác, sử dụng cọc phụ trợ.

Đây là thuật toán đệ quy để giải bài toán này:

Thuật toán Tháp Hà Nội giải quyết bài toán theo cách sau:

1. Di chuyển n - 1 đĩa từ cọc ban đầu qua cọc phụ trợ, sử dụng cọc đích.
2. Di chuyển đĩa còn lại từ cọc ban đầu qua cọc đích.
3. Di chuyển n - 1 đĩa từ cọc phụ trợ qua cọc đích, sử dụng cọc ban đầu.

Ví dụ trên Python

def hanoi_tower(n, source, target, auxiliary):
    if n == 1:
        print(f"Di chuyển đĩa 1 từ {source} đến {target}")
        return
    hanoi_tower(n - 1, source, auxiliary, target)
    print(f"Di chuyển đĩa {n} từ {source} đến {target}")
    hanoi_tower(n - 1, auxiliary, target, source)
        
# Ví dụ sử dụng:
n = 3  # Số lượng đĩa
hanoi_tower(n, 'A', 'C', 'B')
        

Nó hoạt động như thế nào?

Trường hợp cơ bản:

Nếu chỉ có một đĩa (n == 1), nó có thể được di chuyển đơn giản từ cọc ban đầu qua cọc đích.

if n == 1:
    print(f"Di chuyển đĩa 1 từ {source} đến {target}")
    return

Trường hợp đệ quy:

Bước 1. Di chuyển n-1 đĩa từ cọc ban đầu qua cọc phụ trợ, sử dụng cọc đích.

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

Bước 2. Di chuyển đĩa n từ cọc ban đầu qua cọc đích.

print(f"Di chuyển đĩa {n} từ {source} đến {target}")

Bước 3. Di chuyển n - 1 đĩa từ cọc phụ trợ qua cọc đích, sử dụng cọc ban đầu.

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

Ví dụ đầu ra:

Với ba đĩa (n = 3) trên các cọc A, B và C, chương trình sẽ hiển thị:

Di chuyển đĩa 1 từ A đến C
Di chuyển đĩa 2 từ A đến B
Di chuyển đĩa 1 từ C đến B
Di chuyển đĩa 3 từ A đến C
Di chuyển đĩa 1 từ B đến A
Di chuyển đĩa 2 từ B đến C
Di chuyển đĩa 1 từ A đến C

2.3 Bông tuyết Koch

Vẽ bông tuyết bằng cách sử dụng đệ quy là một bài toán thú vị, thường được sử dụng để nghiên cứu về fractals. Một trong những cách đơn giản để vẽ bông tuyết là sử dụng đường cong Koch, là một đường cong fractal.

Thuật toán để vẽ bông tuyết Koch

Đường cong Koch được xây dựng như sau:

• Bắt đầu với một đường thẳng.
• Chia mỗi đoạn thành ba phần và thay thế phần giữa bằng một đường cong nhỏ, trông giống như một "góc cạnh".
• Lặp lại quá trình này một cách đệ quy cho mỗi đoạn.

Hướng dẫn từng bước

• Bắt đầu: Vẽ đoạn thẳng bắt đầu.
• Chia tách: Chia mỗi đoạn thành ba phần.
• Thay thế phần giữa: Trên phần giữa, vẽ một "góc cạnh", gồm hai đường tạo thành một góc 60 độ.
• Lặp lại quá trình: Tiếp tục quá trình này cho mỗi đoạn.

Ví dụ trên Python với thư viện 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)
            
# Cài đặt màn hình
screen = turtle.Screen()
screen.bgcolor("sky blue")
            
# Cài đặt rùa
t = turtle.Turtle()
t.speed(0)
t.color("white")
            
# Vẽ bông tuyết
t.penup()
t.goto(-100, 50)
t.pendown()
draw_snowflake(t, 300, 4)
            
# Kết thúc việc vẽ
turtle.done()
            

Nó hoạt động như thế nào?

1. Hàm draw_koch_curve(t, length, depth):

• t: con rùa vẽ.
• length: chiều dài đoạn thẳng.
• depth: độ sâu đệ quy, xác định mức độ chi tiết.

2. Trường hợp cơ bản:

Nếu depth là 0, con rùa vẽ một đoạn thẳng.

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

3. Trường hợp đệ quy:

Chia đoạn thành ba phần và sử dụng draw_koch_curve đệ quy cho mỗi phần, thêm góc quay.

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. Hàm draw_snowflake(t, length, depth):

Vẽ ba đường cong Koch, nối lại thành một bông tuyết.

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

Làm thế nào để chạy mã?

• Đảm bảo rằng bạn đã cài đặt thư viện Turtle (pip install PythonTurtle).
• Sao chép và dán mã vào một tệp .py và chạy nó. Bạn sẽ thấy bông tuyết được vẽ trên màn hình.

Thuật toán này cho phép hình dung cấu trúc fractal của bông tuyết bằng cách sử dụng các nguyên tắc đệ quy và cấu trúc hình học đơn giản.