Đệ quy trong Python

Khái niệm đệ quy

Đệ quy là một kỹ thuật lập trình trong đó một hàm tự gọi chính nó trực tiếp hoặc gián tiếp để giải quyết một bài toán bằng cách chia nhỏ thành các phần đơn giản hơn. Trong Python, đệ quy thường được sử dụng cho các bài toán có thể chia thành những phần nhỏ có cùng tính chất.

Hàm đệ quy trong Python

Trong Python, một hàm đệ quy được định nghĩa giống như các hàm thông thường nhưng có chứa lời gọi đến chính nó. Cấu trúc của một hàm đệ quy bao gồm điều kiện dừng (base case) để tránh vòng lặp vô hạn và phần gọi đệ quy (recursive case) để tiếp tục xử lý bài toán.

Ví dụ cơ bản về đệ quy:

def giai_thua(n):
    if n == 1:
        return 1
    else:
        return n * giai_thua(n - 1)

print(giai_thua(5))

Kết quả đầu ra:
120

Giải thích:
Giai thừa của một số nguyên dương nn (ký hiệu là n!n!) là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng nn. Trong ví dụ trên, hàm giai_thua(n) gọi chính nó với giá trị nhỏ hơn cho đến khi đạt điều kiện dừng n==1n == 1.

---

Các khái niệm cơ bản về đệ quy

Điều kiện dừng và điều kiện đệ quy

• Điều kiện dừng (Base Case): Đây là điều kiện giúp kết thúc quá trình đệ quy, tránh vòng lặp vô hạn. Ví dụ, trong tính giai thừa, điều kiện dừng là n == 1.
• Điều kiện đệ quy (Recursive Case): Đây là phần của hàm chứa lời gọi chính nó, giúp bài toán tiếp tục được chia nhỏ. Ví dụ, return n * giai_thua(n - 1).

Ví dụ tính dãy Fibonacci bằng đệ quy:

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))

Kết quả đầu ra:
55

Giải thích:

• Điều kiện dừng: Nếu n=0n = 0 trả về 0, nếu n=1n = 1 trả về 1.
• Điều kiện đệ quy: Hàm gọi chính nó hai lần, fibonacci(n-1) + fibonacci(n-2), để tiếp tục tính giá trị của Fibonacci.

---

Các loại đệ quy trong Python

Đệ quy có thể chia thành hai loại chính:

1. Đệ quy đuôi (Tail Recursion): Lời gọi đệ quy là bước cuối cùng của hàm, không có phép toán nào được thực hiện sau khi gọi đệ quy. Điều này giúp tối ưu hóa bộ nhớ.
2. Đệ quy không đuôi (Non-Tail Recursion): Sau khi gọi đệ quy, chương trình vẫn thực hiện thêm các phép toán khác, làm tăng mức sử dụng bộ nhớ.

Ví dụ về hai loại đệ quy:

# Đệ quy đuôi
def tail_fact(n, acc=1):
    if n == 0:
        return acc
    return tail_fact(n - 1, acc * n)

# Đệ quy không đuôi
def nontail_fact(n):
    if n == 1:
        return 1
    return n * nontail_fact(n - 1)

print(tail_fact(5))
print(nontail_fact(5))

Kết quả đầu ra:
120
120

---

So sánh đệ quy và vòng lặp

Tiêu chí	Đệ quy	Vòng lặp
Dễ hiểu	Dễ hơn khi giải quyết bài toán có tính đệ quy tự nhiên như cây, DFS, Fibonacci	Khó hơn khi áp dụng cho bài toán phức tạp
Hiệu suất bộ nhớ	Tốn nhiều bộ nhớ hơn do lưu nhiều trạng thái trên stack	Tiết kiệm bộ nhớ hơn do không cần stack bổ sung
Hiệu suất thực thi	Chậm hơn do tốn thời gian gọi và quay lui hàm	Nhanh hơn do không phải thực hiện nhiều lần gọi hàm

---

Ưu điểm của đệ quy

✔ Mã nguồn ngắn gọn, dễ hiểu: Giúp biểu diễn thuật toán theo cách tự nhiên và đơn giản hơn.
✔ Hữu ích cho bài toán phức tạp: Đặc biệt phù hợp với các bài toán liên quan đến cây, đồ thị, chuỗi, v.v.

Nhược điểm của đệ quy

❌ Tốn bộ nhớ: Mỗi lần gọi đệ quy tạo ra một khung ngăn xếp mới, có thể dẫn đến lỗi tràn ngăn xếp (stack overflow).
❌ Chậm hơn so với vòng lặp: Do tốn thời gian cho quá trình gọi hàm và quản lý stack.

---

Tóm lại, đệ quy là một kỹ thuật lập trình mạnh mẽ, giúp giải quyết các bài toán phức tạp theo cách đơn giản hơn. Tuy nhiên, cần cân nhắc khi sử dụng để tránh ảnh hưởng đến hiệu suất và bộ nhớ.

Menu Python>>