Đệ quy trong Python: Khái niệm, Ví dụ và Mẹo

Đệ quy là một khái niệm nền tảng trong lập trình và có ý nghĩa đặc biệt trong Python. Đây là kỹ thuật mà một hàm tự gọi lại chính nó để giải bài toán bằng cách chia nhỏ thành các bài toán con dễ xử lý hơn. 

Phương pháp này cho phép tạo ra lời giải súc tích và thanh thoát, đặc biệt khi xử lý các vấn đề có tính lặp lại hoặc cấu trúc phân cấp. Trong Python, đệ quy được dùng trong nhiều ứng dụng, từ sắp xếp thuật toán cho đến duyệt dữ liệu phức tạp. 

Lời giải đệ quy thường phản chiếu định nghĩa toán học của vấn đề, nên trực quan với những ai quen tư duy toán học. Vẻ đẹp của đệ quy nằm ở khả năng diễn đạt thuật toán phức tạp chỉ bằng vài dòng mã, vừa thanh thoát vừa dễ đọc. Tuy nhiên, nắm vững đệ quy đòi hỏi thay đổi cách nghĩ so với tiếp cận lặp thông thường.

Trong bài viết này, tôi sẽ khám phá khái niệm đệ quy, cách nó hoạt động trong Python và các ứng dụng thực tiễn, bao gồm thảo luận về các vấn đề thường gặp và so sánh với lặp. Nếu bạn mới học Python, hãy cân nhắc tham gia một số khóa học của chúng tôi như Giới thiệu về Python, Các khái niệm về mô hình lập trình, hoặc Nền tảng lập trình Python.

Đệ quy trong Python là gì?

Trong Python, đệ quy là việc một hàm tự gọi lại chính nó để giải quyết bài toán. Nó gồm hai thành phần then chốt:

• Điều kiện dừng (base case): Điều kiện chấm dứt việc đệ quy. Nếu thiếu, các lời gọi đệ quy sẽ tiếp diễn vô hạn và cuối cùng gây treo hàm hoặc cạn bộ nhớ.
• Trường hợp đệ quy (recursive case): Phần này chia nhỏ bài toán và gọi lại hàm với các phần nhỏ đó.

Một cách hình dung đơn giản về đệ quy: tưởng tượng một hàm giải bài toán phức tạp bằng cách giải các phiên bản nhỏ hơn của chính bài toán đó, cuối cùng đạt tới một nghiệm không cần đệ quy thêm nữa.

Tiếp cận đệ quy tuân theo chiến lược "chia để trị", phân rã vấn đề phức tạp thành phiên bản đơn giản cho tới khi gặp trường hợp tầm thường. Cách này thường phản chiếu cách chúng ta tự nhiên nghĩ về việc giải quyết vấn đề. Ví dụ, khi sắp xếp một bộ bài, ta có xu hướng sắp xếp các nhóm nhỏ rồi ghép lại — về bản chất chính là cách thuật toán sắp xếp đệ quy như merge sort hoạt động.

Mọi hàm đệ quy đều phải có ít nhất một điều kiện dừng và ít nhất một trường hợp đệ quy. Điều kiện dừng ngăn đệ quy vô hạn bằng cách cung cấp một trạng thái không cần gọi thêm hàm. Trường hợp đệ quy thu nhỏ kích thước bài toán qua mỗi lần gọi, đảm bảo cuối cùng sẽ chạm đến điều kiện dừng.

Đệ quy hoạt động như thế nào trong Python?

Đệ quy cho phép một hàm tự gọi lại với các tham số đã được điều chỉnh, dần dần giải quyết bài toán theo từng bước nhỏ. Để hiểu cụ thể hơn, hãy xét nhiệm vụ tính tổng các số từ 1 đến num.

Dưới đây là một cách tiếp cận đệ quy đơn giản để tính tổng:

def sum_recursive(num):
    if num == 1:  # Base case
        return num
    return num + sum_recursive(num - 1)  # Recursive case

print(sum_recursive(3)) # 3 + 2 + 1 Được hỗ trợ bởi

6Được hỗ trợ bởi

Trong hàm này, điều kiện dừng là khi num == 1, giúp dừng đệ quy. Nếu không, hàm sẽ tự gọi lại với num - 1 cho tới khi gặp điều kiện dừng.

Cách hoạt động theo từng bước:

1. sum_recursive(3) gọi sum_recursive(2).
2. sum_recursive(2) gọi sum_recursive(1).
3. sum_recursive(1) trả về 1 (điều kiện dừng).
4. Lúc này, sum_recursive(2) trả về 2 + 1 = 3, và sum_recursive(3) trả về 3 + 3 = 6.

Một ví dụ khác là hàm đệ quy tính lũy thừa của một số:

def power(base, exponent):
    if exponent == 0:  # Base case
        return 1
    else:
        return base * power(base, exponent - 1)  # Recursive case

print(power(2, 3))Được hỗ trợ bởi

8Được hỗ trợ bởi

Giải thích từng bước của hàm lũy thừa này:

• power(2, 3) gọi power(2, 2).
• power(2, 2) gọi power(2, 1).
• power(2, 1) gọi power(2, 0).
• power(2, 0) trả về 1 (điều kiện dừng).
• Quay ngược lại: power(2, 1) trả về 2 * 1 = 2.
• Sau đó power(2, 2) trả về 2 * 2 = 4.
• Cuối cùng, power(2, 3) trả về 2 * 4 = 8.

Khi một hàm đệ quy được gọi, mỗi lần gọi sẽ tạo một mục mới trên call stack. Ngăn xếp này lưu vết tất cả lời gọi hàm và biến của chúng. Khi gặp điều kiện dừng, ngăn xếp bắt đầu giải kết quả theo thứ tự ngược, tính toán kết quả cuối cùng từng bước một.

Hiểu hành vi của ngăn xếp là tối quan trọng vì nó giải thích cả sức mạnh lẫn giới hạn của đệ quy trong Python. Nó lưu ngữ cảnh một cách thanh lịch nhưng cũng có thể dẫn đến vấn đề bộ nhớ khi đệ quy quá sâu.

Cài đặt giai thừa trong Python bằng đệ quy

Hàm giai thừa là ví dụ kinh điển để minh họa đệ quy. Giai thừa của số n, ký hiệu n!, là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng n. Về mặt toán học:

n! = n × (n − 1) × (n − 2) × … × 1

Ở dạng đệ quy, hàm giai thừa có thể được định nghĩa như sau:

n! = n × (n − 1)!

Hãy triển khai điều này trong Python:

def compute_factorial(num):
    if num == 0:  # Base case
        return 1
    return num * compute_factorial(num - 1)  # Recursive case

print(compute_factorial(4)) # 4 * 3 * 2 * 1Được hỗ trợ bởi

24Được hỗ trợ bởi

Giải thích từng bước của đoạn mã:

• Hàm compute_factorial(num) kiểm tra nếu num == 0 thì trả về 1.
• Nếu không, hàm trả về num * compute_factorial(num - 1), trong đó hàm tự gọi lại với giá trị num nhỏ hơn.

Hàm giai thừa minh họa hoàn hảo sự thanh thoát của đệ quy. Định nghĩa toán học vốn đã mang tính đệ quy, khiến việc hiện thực hóa thành mã vừa trực quan vừa sát với khái niệm toán. Đây là một trong những điểm mạnh của đệ quy: cho phép mã diễn đạt trực tiếp các định nghĩa toán học.

Cũng cần lưu ý một số trường hợp biên. Chẳng hạn, giai thừa thường chỉ được định nghĩa cho số nguyên không âm. Một hiện thực vững vàng có thể cần xử lý lỗi với đầu vào âm hoặc kiểm tra kiểu dữ liệu. 

Ngoài ra, với giá trị num lớn, lời giải đệ quy có thể dẫn đến tràn ngăn xếp — một hạn chế tôi sẽ bàn kỹ hơn.

Vấn đề thường gặp: Cách khắc phục lỗi đệ quy trong Python

Mặc dù đệ quy là công cụ mạnh mẽ, nó dễ gặp một số vấn đề phổ biến như:

Vượt quá độ sâu đệ quy tối đa

Python đặt giới hạn đệ quy mặc định là 1000 lần gọi. Nếu một hàm đệ quy tự gọi quá nhiều lần, sẽ phát sinh RecursionError.

Cách khắc phục:

Bạn có thể tăng độ sâu đệ quy bằng sys.setrecursionlimit(). Tuy nhiên, không khuyến nghị trừ khi thật cần thiết vì có thể gây tràn ngăn xếp.

import sys  

# Get the current recursion limit
current_limit = sys.getrecursionlimit()
print(f'Current limit: {current_limit}')  

# Set a new recursion limit to 200
new_limit = 200
sys.setrecursionlimit(new_limit)  

# Get the new recursion limit
changed_current_limit = sys.getrecursionlimit()
print(f'Current limit after change: {changed_current_limit}')  Được hỗ trợ bởi

Current limit: 1000
Current limit after change: 200Được hỗ trợ bởi

Thiếu điều kiện dừng

Thiếu hoặc định nghĩa sai điều kiện dừng sẽ khiến hàm đệ quy vô hạn, dẫn tới tràn ngăn xếp.

Để khắc phục, hãy đảm bảo điều kiện dừng được định nghĩa rõ ràng và có thể đạt đến.

Cách dừng đệ quy trong Python

Chìa khóa để dừng đệ quy trong Python là xác định điều kiện dừng phù hợp. Nếu thiếu, đệ quy sẽ không bao giờ kết thúc và gây lỗi.

Ví dụ, trong hàm giai thừa tôi triển khai ở trên, điều kiện dừng là if num == 0, giúp chấm dứt đệ quy. Nhìn chung, bạn cần đảm bảo mỗi hàm đệ quy đều có điều kiện để dừng.

Thiết kế điều kiện dừng hiệu quả đòi hỏi cân nhắc kỹ. Một số hướng dẫn gồm:

• Xác định phiên bản đơn giản nhất của bài toán có thể giải trực tiếp.
• Đảm bảo mọi nhánh đệ quy cuối cùng đều đi tới điều kiện dừng.
• Kiểm thử riêng các trường hợp biên để xác nhận xử lý đúng.
• Cân nhắc nhiều điều kiện dừng nếu bài toán yêu cầu.

Đôi khi, kỹ thuật lập trình phòng thủ hữu ích, như thêm lớp bảo vệ với đầu vào không hợp lệ hoặc kiểm tra lúc chạy để ngăn độ sâu đệ quy quá mức. Ví dụ:

def safe_factorial(num, depth=0, max_depth=100):
    # Check if recursion is too deep
    if depth > max_depth:
        raise ValueError("Maximum recursion depth exceeded")
   
    # Base case
    if num <= 0:
        return 1
   
    # Recursive case with depth tracking
    return num * safe_factorial(num - 1, depth + 1, max_depth)Được hỗ trợ bởi

# Calculate factorial of 5 with default depth limits
result = safe_factorial(5)

print(result) Được hỗ trợ bởi

120Được hỗ trợ bởi

# Calculate factorial of 5 with depth > max_depth
result = safe_factorial(5, depth=20, max_depth=10)

print(result) Được hỗ trợ bởi

ValueError: Maximum recursion depth exceededĐược hỗ trợ bởi

Cách tiếp cận này cho phép bạn đặt giới hạn tùy chỉnh và cung cấp thông báo lỗi có ý nghĩa hơn so với RecursionError mặc định.

Dưới đây là một ví dụ khác minh họa cách định nghĩa điều kiện dừng theo một kiểu khác: tìm ước số chung lớn nhất (GCD) của hai số bằng đệ quy.

GCD của hai số x và y có thể tính bằng thuật toán Euclid, với toán tử chia lấy dư %:

• Điều kiện dừng: Nếu y == 0, thì GCD là x.
• Trường hợp đệ quy: Ngược lại, GCD của x và y bằng GCD của y và x % y.

def find_gcd(x, y):
    # Base case: if y is 0, the GCD is x
    if y == 0:
        return x
    # Recursive case: GCD of y and x % y
    return find_gcd(y, x % y)

print(find_gcd(48, 18))  Được hỗ trợ bởi

6Được hỗ trợ bởi

Đệ quy so với lặp trong Python

Cả đệ quy và lặp đều có thể giải nhiều vấn đề giống nhau, nhưng mỗi cách đều có ưu và nhược điểm:

• Đệ quy thường thanh thoát và dễ hiểu hơn, đặc biệt với các vấn đề có cấu trúc đệ quy tự nhiên (ví dụ duyệt cây, giai thừa, dãy Fibonacci).
• Lặp có thể hiệu quả hơn vì không tốn chi phí nhiều lần gọi hàm và tránh được vấn đề tràn ngăn xếp. Lời giải lặp thường tiết kiệm bộ nhớ hơn.

Khi nào nên dùng đệ quy:

• Khi bài toán có thể tự nhiên chia thành các bài toán con nhỏ hơn.
• Với các cấu trúc dữ liệu phân cấp như cây.
• Khi lời giải ở dạng đệ quy trực quan hơn và dẫn đến mã sạch hơn.
• Khi ưu tiên tính dễ đọc của mã hơn tối ưu hiệu năng.
• Khi làm việc với dữ liệu có độ sâu không xác định (như phân tích JSON hoặc XML lồng nhau).

Khi nào nên dùng lặp:

• Với các vấn đề cần thao tác lặp lại mà không cần chia nhỏ thành bài toán con.
• Với tác vụ cần hiệu năng cao, nơi đệ quy sâu có thể gây tốn bộ nhớ.
• Khi làm việc với tập dữ liệu lớn có thể vượt giới hạn đệ quy.
• Khi mối quan tâm chính là sử dụng bộ nhớ.
• Với các vấn đề mang tính tuần tự hơn là phân cấp.

Hãy so sánh hai cách cài đặt đệ quy và lặp cho cùng một bài toán: tính tổng các số từ 1 đến num:

Đệ quy:

def sum_recursive(num):
    if num == 1:
        return 1
    else:
        return num + sum_recursive(num - 1)Được hỗ trợ bởi

Lặp:

def iterative_sum(num):
    total = 0
    for i in range(1, num + 1):
        total += i
    return totalĐược hỗ trợ bởi

Phiên bản lặp dùng vòng lặp để cộng dồn tổng, còn phiên bản đệ quy chia bài toán thành việc cộng n với tổng các số từ 1 đến num - 1. Cả hai đều đúng, nhưng với num lớn, phiên bản lặp hiệu quả hơn vì không tốn chi phí nhiều lần gọi hàm.

Một số bài toán vốn mang tính đệ quy có thể chuyển thành lời giải lặp bằng cách dùng ngăn xếp hoặc hàng đợi để mô phỏng các lời gọi đệ quy. Kỹ thuật này đặc biệt hữu ích khi duyệt cây hoặc đồ thị.

Ví dụ thực tiễn về đệ quy trong Python

Đệ quy có thể áp dụng cho nhiều bài toán thú vị:

1. Tính các số Fibonacci

Dãy Fibonacci được định nghĩa đệ quy như sau:

• F(0) = 0
• F(1) = 1
• F(n) = F(n − 1) + F(n − 2)

Dãy số nhận được như sau:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

Có thể triển khai như sau:

def compute_fibonacci(num):
    if num <= 0:
        return 0
    elif num == 1:
        return 1
    return compute_fibonacci(num - 1) + compute_fibonacci(num - 2)

print(compute_fibonacci(6))Được hỗ trợ bởi

8Được hỗ trợ bởi

Tuy nhiên, cách làm ngây thơ này tính lặp lại nhiều giá trị. Cách hiệu quả hơn là dùng memoization để lưu kết quả đã tính (bộ nhớ đệm) nhằm tránh tính toán thừa và giảm đáng kể thời gian xử lý:

def optimized_fibonacci(num, cache=None):
    if cache is None:
        cache = {}
    if num in cache:
        return cache[num]
    if num <= 1:
        return num
    cache[num] = optimized_fibonacci(num - 1, cache) + optimized_fibonacci(num - 2, cache)
    return cache[num]Được hỗ trợ bởi

Ta có thể đơn giản hóa hơn nữa bằng bộ trang trí lru_cache() từ mô-đun functools:

from functools import lru_cache

@lru_cache(maxsize=None)  # Cache all computed values
def cached_fibonacci(num):
    if num <= 1:
        return num
    return cached_fibonacci(num - 1) + cached_fibonacci(num - 2)Được hỗ trợ bởi

2. Duyệt cấu trúc dữ liệu lồng nhau

Đệ quy cũng rất hữu ích khi làm việc với cấu trúc dữ liệu lồng nhau như danh sách của danh sách hoặc đối tượng JSON. Ví dụ, duyệt cây thư mục hoặc làm phẳng một danh sách lồng nhau.

def flatten(nested):
    result = []
    for element in nested:
        if isinstance(element, list):
            result.extend(flatten(element))
        else:
            result.append(element)
    return result

nested_structure = [1, [2, 3], [4, [5, 6]]]

print(flatten(nested_structure))  Được hỗ trợ bởi

[1, 2, 3, 4, 5, 6]Được hỗ trợ bởi

3. Thuật toán sắp xếp (ví dụ, quick sort hoặc merge sort) 

Các thuật toán sắp xếp như quick sort và merge sort phụ thuộc nhiều vào đệ quy. Trong các thuật toán này, bài toán được chia thành các bài toán con nhỏ hơn, rồi sắp xếp đệ quy.

Dưới đây là một hiện thực quicksort đơn giản:

def quicksort_algo(array):
    if len(array) <= 1:
        return array
    pivot = array[len(array) // 2]
    lower = [item for item in array if item < pivot]
    equal = [item for item in array if item == pivot]
    greater = [item for item in array if item > pivot]
    return quicksort_algo(lower) + equal + quicksort_algo(greater)

array = [220, 33, 400, 150, 16]

print(quicksort_algo(array))Được hỗ trợ bởi

[16, 33, 150, 220, 400]Được hỗ trợ bởi

Kết luận

Đệ quy là một khái niệm mạnh mẽ trong Python, giúp giải bài toán phức tạp bằng cách chia nhỏ thành các bài toán con đơn giản hơn. Nếu dùng đúng cách, đệ quy mang lại mã nguồn sạch, gọn và dễ hiểu. 

Tuy nhiên, điều quan trọng là xác định điều kiện dừng phù hợp và chú ý đến độ sâu đệ quy để tránh các lỗi thường gặp. 

Dù đôi khi kém hiệu quả hơn so với lặp, đệ quy vẫn là công cụ vô giá cho một số loại bài toán, đặc biệt là những bài liên quan đến dữ liệu phân cấp hoặc tự nhiên phù hợp với lời giải đệ quy.

Bằng cách hiểu đệ quy và luyện tập qua các ví dụ như giai thừa, dãy Fibonacci và thuật toán sắp xếp, bạn sẽ có đủ hành trang để khai thác đệ quy trong các dự án Python của mình.

Nếu bạn quan tâm tới các chủ đề Python nâng cao nơi có thể áp dụng đệ quy, hãy xem các lộ trình học sau: Lập trình Python, Chuyên viên phân tích dữ liệu bằng Python, và Nhà khoa học dữ liệu liên kết bằng Python