Bài 2.19 - Đệ quy Python cơ bản

Chào mừng các bạn đến với thế giới thú vị của đệ quy trong Python! Đây là một khái niệm mạnh mẽ, đôi khi hơi "hack não" nhưng lại cực kỳ hữu ích trong lập trình. Đệ quy không chỉ là một kỹ thuật, mà còn là một cách tư duy để giải quyết vấn đề bằng cách chia nhỏ nó thành các vấn đề con giống hệt nhưng đơn giản hơn.

Hãy tưởng tượng bạn có một con búp bê Nga Matryoshka. Mở con lớn nhất ra, bạn thấy một con nhỏ hơn bên trong, giống hệt con lớn. Mở tiếp con nhỏ hơn, bạn lại thấy một con nhỏ hơn nữa... Cứ thế cho đến khi bạn gặp con nhỏ nhất, không thể mở được nữa. Đệ quy hoạt động theo một nguyên tắc tương tự: một hàm tự gọi lại chính nó với một phiên bản nhỏ hơn của vấn đề, cho đến khi gặp một trường hợp cơ bản, đơn giản nhất có thể giải quyết trực tiếp.

Đệ quy là gì?

Trong lập trình, đệ quy (recursion) là hiện tượng một hàm tự gọi lại chính nó trong định nghĩa của hàm đó. Thay vì sử dụng vòng lặp (như for hoặc while) để lặp đi lặp lại một hành động, hàm đệ quy giải quyết vấn đề bằng cách:

Giải quyết một phần nhỏ của vấn đề.
Gọi lại chính nó để giải quyết phần còn lại (phiên bản nhỏ hơn của vấn đề ban đầu).
Quá trình này lặp lại cho đến khi đạt đến một điều kiện dừng (base case) - trường hợp đơn giản nhất mà hàm có thể trả về kết quả trực tiếp mà không cần gọi lại chính nó nữa.

Điều kiện dừng là cực kỳ quan trọng. Nếu không có nó, hàm sẽ tự gọi chính nó mãi mãi, dẫn đến lỗi tràn bộ nhớ stack (Stack Overflow). Giống như việc bạn không bao giờ tìm thấy con búp bê Nga nhỏ nhất vậy!

Cấu trúc của một hàm đệ quy

Một hàm đệ quy luôn luôn phải có hai thành phần chính:

Điều kiện dừng (Base Case): Đây là trường hợp (hoặc các trường hợp) mà hàm có thể trả về kết quả trực tiếp mà không cần gọi đệ quy thêm nữa. Nó ngăn chặn việc hàm tự gọi vô hạn.
Bước đệ quy (Recursive Step): Đây là phần mà hàm thực hiện một số tính toán và sau đó gọi lại chính nó với một đầu vào đã được thay đổi (thường là làm cho vấn đề nhỏ đi) để tiến gần hơn đến điều kiện dừng.

Hãy cùng xem xét một vài ví dụ kinh điển để hiểu rõ hơn.

Ví dụ 1: Tính Giai thừa (Factorial)

Giai thừa của một số nguyên không âm n, ký hiệu là n!, là tích của tất cả các số nguyên dương từ 1 đến n. Theo định nghĩa:

0! = 1
n! = n (n-1) (n-2) ... 1 (với n > 0)

Chúng ta có thể thấy một cấu trúc đệ quy ở đây:

n! = n * (n-1)!

Đây chính là ý tưởng để viết hàm đệ quy tính giai thừa:

Điều kiện dừng: Nếu n = 0 hoặc n = 1, kết quả là 1.
Bước đệ quy: Nếu n > 1, kết quả là n nhân với giai thừa của (n-1).

def tinh_giai_thua(n):
    """
    Hàm đệ quy tính giai thừa của số nguyên không âm n.
    """
    # --- Điều kiện dừng (Base Case) ---
    if n < 0:
        # Giai thừa không xác định cho số âm, có thể raise lỗi hoặc trả về giá trị đặc biệt
        return "Giai thừa không xác định cho số âm" 
    elif n == 0 or n == 1:
        print(f"Giai thừa({n}) đạt điều kiện dừng, trả về 1")
        return 1
    # --- Bước đệ quy (Recursive Step) ---
    else:
        print(f"Tính Giai thừa({n}) = {n} * Giai thừa({n-1})")
        # Hàm gọi lại chính nó với n-1
        ket_qua_buoc_truoc = tinh_giai_thua(n - 1) 
        ket_qua = n * ket_qua_buoc_truoc
        print(f"Giai thừa({n}) tính xong, trả về {ket_qua}")
        return ket_qua

# Thử nghiệm
so_can_tinh = 4
print(f"\nBắt đầu tính giai thừa của {so_can_tinh}:")
ket_qua_cuoi_cung = tinh_giai_thua(so_can_tinh)
print(f"\nKết quả cuối cùng: {so_can_tinh}! = {ket_qua_cuoi_cung}")

Giải thích cách hoạt động (với tinh_giai_thua(4)):

tinh_giai_thua(4) được gọi. n=4 không phải là 0 hoặc 1. Nó sẽ tính 4 * tinh_giai_thua(3).
tinh_giai_thua(3) được gọi. n=3 không phải là 0 hoặc 1. Nó sẽ tính 3 * tinh_giai_thua(2).
tinh_giai_thua(2) được gọi. n=2 không phải là 0 hoặc 1. Nó sẽ tính 2 * tinh_giai_thua(1).
tinh_giai_thua(1) được gọi. n=1, đây là điều kiện dừng. Hàm trả về 1.
Quay lại bước 3: tinh_giai_thua(2) nhận được kết quả 1 từ tinh_giai_thua(1). Nó tính 2 * 1 = 2 và trả về 2.
Quay lại bước 2: tinh_giai_thua(3) nhận được kết quả 2 từ tinh_giai_thua(2). Nó tính 3 * 2 = 6 và trả về 6.
Quay lại bước 1: tinh_giai_thua(4) nhận được kết quả 6 từ tinh_giai_thua(3). Nó tính 4 * 6 = 24 và trả về 24.

Kết quả cuối cùng là 24. Bạn có thể thấy hàm tự "mở" các lời gọi cho đến khi gặp điều kiện dừng, sau đó "đóng" lại từng bước để tính toán kết quả cuối cùng.

Ví dụ 2: Dãy Fibonacci

Dãy Fibonacci là một dãy số nổi tiếng trong đó mỗi số là tổng của hai số liền trước nó. Dãy thường bắt đầu bằng 0 và 1. F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) với n > 1

Công thức này gần như là một định nghĩa đệ quy hoàn hảo!

Điều kiện dừng: Nếu n = 0, trả về 0. Nếu n = 1, trả về 1.
Bước đệ quy: Nếu n > 1, trả về tổng của fibonacci(n-1) và fibonacci(n-2).

def fibonacci(n):
    """
    Hàm đệ quy tính số Fibonacci thứ n.
    """
    # --- Điều kiện dừng (Base Cases) ---
    if n <= 0:
        # print(f"Fibonacci({n}) đạt điều kiện dừng (<=0), trả về 0")
        return 0
    elif n == 1:
        # print(f"Fibonacci({n}) đạt điều kiện dừng (==1), trả về 1")
        return 1
    # --- Bước đệ quy (Recursive Step) ---
    else:
        # print(f"Tính Fibonacci({n}) = Fibonacci({n-1}) + Fibonacci({n-2})")
        # Hàm gọi lại chính nó hai lần
        return fibonacci(n - 1) + fibonacci(n - 2)

# Thử nghiệm
vi_tri = 6 
print(f"\nTính số Fibonacci tại vị trí {vi_tri}:")
ket_qua_fib = fibonacci(vi_tri)
print(f"F({vi_tri}) = {ket_qua_fib}") 

# In ra vài số đầu tiên
print("\nMột vài số Fibonacci đầu tiên:")
for i in range(10):
    print(f"F({i}) = {fibonacci(i)}")

Giải thích và Lưu ý:

Hàm fibonacci(n) này rất thanh lịch và thể hiện chính xác định nghĩa toán học. Tuy nhiên, nó cực kỳ không hiệu quả!

Hãy xem xét việc tính fibonacci(5):

fibonacci(5) gọi fibonacci(4) và fibonacci(3)
fibonacci(4) gọi fibonacci(3) và fibonacci(2)
fibonacci(3) (lần đầu) gọi fibonacci(2) và fibonacci(1)
fibonacci(3) (lần hai, từ fibonacci(4)) lại gọi fibonacci(2) và fibonacci(1)
... bạn có thể thấy fibonacci(3), fibonacci(2) bị tính toán lặp đi lặp lại rất nhiều lần.

Điều này dẫn đến thời gian chạy tăng theo hàm mũ. Với các giá trị n lớn (ví dụ n=40), hàm này sẽ chạy rất chậm. Đây là một ví dụ điển hình về việc đệ quy có thể đẹp nhưng không phải lúc nào cũng là giải pháp tốt nhất về mặt hiệu năng nếu không được tối ưu (ví dụ bằng kỹ thuật memoization hoặc dynamic programming - quy hoạch động).

Ví dụ 3: Tính tổng các phần tử trong danh sách (List)

Giả sử bạn muốn tính tổng các số trong một danh sách bằng đệ quy. Ý tưởng là:

Tổng của một danh sách = phần tử đầu tiên + tổng của phần còn lại của danh sách.
Điều kiện dừng: Nếu danh sách rỗng, tổng là 0.
Bước đệ quy: Lấy phần tử đầu tiên, cộng với kết quả của việc gọi đệ quy hàm tính tổng cho phần còn lại của danh sách (từ phần tử thứ hai trở đi).

def tinh_tong_list(data):
    """
    Hàm đệ quy tính tổng các phần tử trong một danh sách (list).
    """
    # --- Điều kiện dừng ---
    if not data: # Kiểm tra xem danh sách có rỗng không (len(data) == 0)
        # print("Danh sách rỗng, trả về 0")
        return 0
    # --- Bước đệ quy ---
    else:
        phan_tu_dau = data[0]
        phan_con_lai = data[1:] # Lấy list con từ phần tử thứ 2 trở đi
        # print(f"Tính tổng: {phan_tu_dau} + Tổng({phan_con_lai})")
        # Gọi đệ quy cho phần còn lại của danh sách
        tong_phan_con_lai = tinh_tong_list(phan_con_lai)
        ket_qua = phan_tu_dau + tong_phan_con_lai
        # print(f"Trả về tổng tạm thời: {ket_qua}")
        return ket_qua

# Thử nghiệm
my_list = [1, 5, 3, 9, 2]
print(f"\nTính tổng của danh sách: {my_list}")
tong = tinh_tong_list(my_list)
print(f"Tổng các phần tử là: {tong}")

Giải thích:

tinh_tong_list([1, 5, 3, 9, 2]) -> 1 + tinh_tong_list([5, 3, 9, 2])
tinh_tong_list([5, 3, 9, 2]) -> 5 + tinh_tong_list([3, 9, 2])
tinh_tong_list([3, 9, 2]) -> 3 + tinh_tong_list([9, 2])
tinh_tong_list([9, 2]) -> 9 + tinh_tong_list([2])
tinh_tong_list([2]) -> 2 + tinh_tong_list([])
tinh_tong_list([]) -> Danh sách rỗng, gặp điều kiện dừng, trả về 0.
Quay lại bước 5: nhận 0, trả về 2 + 0 = 2.
Quay lại bước 4: nhận 2, trả về 9 + 2 = 11.
Quay lại bước 3: nhận 11, trả về 3 + 11 = 14.
Quay lại bước 2: nhận 14, trả về 5 + 14 = 19.
Quay lại bước 1: nhận 19, trả về 1 + 19 = 20.

Kết quả cuối cùng là 20.

Ưu điểm và Nhược điểm của Đệ quy

Đệ quy là một công cụ mạnh mẽ, nhưng cần được sử dụng một cách khôn ngoan.

Ưu điểm:

Thanh lịch và Dễ đọc (đối với các bài toán phù hợp): Code đệ quy thường ngắn gọn và phản ánh trực tiếp cấu trúc logic hoặc toán học của vấn đề (như giai thừa, Fibonacci).
Giải quyết các vấn đề phức tạp: Rất hiệu quả cho các cấu trúc dữ liệu đệ quy như cây (trees) hoặc các bài toán chia để trị (divide and conquer) như sắp xếp nhanh (Quicksort), sắp xếp trộn (Mergesort).
Tư duy tự nhiên: Giúp chia nhỏ vấn đề lớn thành các vấn đề con giống hệt nhau, dễ quản lý hơn.

Nhược điểm:

Chi phí bộ nhớ và hiệu năng: Mỗi lần gọi hàm đệ quy, Python cần lưu trạng thái hiện tại (biến cục bộ, địa chỉ trả về) vào call stack. Với các lời gọi đệ quy sâu, điều này tốn bộ nhớ stack và thời gian thực thi cho việc gọi hàm.
Nguy cơ tràn bộ nhớ Stack (Stack Overflow): Python có giới hạn về độ sâu của stack đệ quy (thường khoảng 1000 lần gọi). Nếu hàm đệ quy gọi chính nó quá nhiều lần mà không đạt điều kiện dừng (hoặc điều kiện dừng quá xa), nó sẽ gây ra lỗi RecursionError: maximum recursion depth exceeded.
Khó Debugging: Việc theo dõi luồng thực thi qua nhiều cấp độ đệ quy có thể phức tạp hơn so với vòng lặp thông thường.
Không hiệu quả (đôi khi): Như đã thấy với ví dụ Fibonacci, một giải pháp đệ quy ngây thơ có thể thực hiện lại các tính toán giống nhau nhiều lần, dẫn đến lãng phí tài nguyên.

Khi nào nên sử dụng Đệ quy?

Hãy cân nhắc sử dụng đệ quy khi:

Vấn đề có bản chất đệ quy rõ ràng, ví dụ như thao tác trên cây nhị phân, duyệt thư mục tập tin, các thuật toán chia để trị.
Giải pháp đệ quy đơn giản và dễ hiểu hơn đáng kể so với giải pháp lặp (dùng vòng lặp).
Hiệu năng và giới hạn bộ nhớ stack không phải là yếu tố quá quan trọng, hoặc độ sâu đệ quy được dự đoán là không quá lớn.
Bạn có thể dễ dàng xác định được điều kiện dừng rõ ràng.

Trong nhiều trường hợp, một giải pháp dùng vòng lặp (iterative) có thể hiệu quả hơn về mặt bộ nhớ và tốc độ. Tuy nhiên, hiểu biết về đệ quy là một kỹ năng quan trọng của lập trình viên, giúp bạn có thêm một công cụ mạnh mẽ để giải quyết vấn đề và hiểu sâu hơn về cách hoạt động của các thuật toán phức tạp.

Hãy thử tự mình viết lại các ví dụ trên hoặc tìm thêm các bài toán khác có thể giải bằng đệ quy (ví dụ: tìm ước chung lớn nhất, đảo ngược chuỗi, tháp Hà Nội...) để luyện tập kỹ năng này nhé!

Comments

There are no comments at the moment.