Python - Đệ Quy: Hướng Dẫn Cho Người Mới Bắt Đầu

Xin chào bạn, những phù thủy Python tương lai! Hôm nay, chúng ta sẽ bắt đầu hành trình thú vị vào thế giới của đệ quy. Đừng lo lắng nếu điều này có vẻ quá khó khăn – tôi hứa sẽ làm cho nó trở nên thú vị và dễ hiểu. Vậy, hãy lấy ly đồ uống yêu thích của bạn, thoải mái ngồi và hãy bắt đầu!

Đệ Quy Là Gì?

Hãy tưởng tượng bạn đứng giữa hai chiếc gương đối diện với nhau. Bạn thấy vô số các hình ảnh phản chiếu, phải không? Đó hơi tương tự như đệ quy trong lập trình! Đơn giản, đệ quy là khi một hàm gọi chính nó để giải quyết một vấn đề.

Hãy bắt đầu với một ví dụ đơn giản:

def dem_nhay(n):
if n <= 0:
print("Blastoff!")
else:
print(n)
dem_nhay(n - 1)

dem_nhay(5)

Nếu bạn chạy mã này, bạn sẽ thấy:

5
4
3
2
1
Blastoff!

Bây giờ, hãy phân tích điều này:

1. Chúng ta định nghĩa một hàm có tên dem_nhay nhận vào một số n.
2. Nếu n là 0 hoặc nhỏ hơn, chúng ta in ra "Blastoff!"
3. Nếu không, chúng ta in ra n và sau đó gọi lại dem_nhay với n - 1.

Đó là đệ quy đang hoạt động! Hàm sẽ liên tục gọi chính nó với một số nhỏ hơn cho đến khi đạt đến số 0.

Các Thành Phần Của Đệ Quy

Mỗi hàm đệ quy có hai thành phần chính:

1. Trường Hợp Cơ Sở: Đây là điều kiện dừng đệ quy.
2. Trường Hợp Đệ Quy: Đây là nơi hàm gọi chính nó.

Trong ví dụ đếm ngược của chúng ta:

• Trường hợp cơ sở là if n <= 0
• Trường hợp đệ quy là dem_nhay(n - 1)

Hãy xem một ví dụ kinh điển khác: tính giai thừa.

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

print(giai_thua(5))  # Output: 120

Đây là điều gì đang diễn ra:

1. Nếu n là 0 hoặc 1, chúng ta trả về 1 (đây là trường hợp cơ sở của chúng ta).
2. Nếu không, chúng ta nhân n với giai thừa của n - 1 (đây là trường hợp đệ quy của chúng ta).

Vậy giai_thua(5) trở thành: 5 giai_thua(4) 5 (4 giai_thua(3)) 5 (4 (3 giai_thua(2))) 5 (4 (3 (2 giai_thua(1)))) 5 (4 (3 (2 1))) 5 4 3 2 1 = 120

Sức Mạnh Của Đệ Quy

Đệ quy có thể làm cho một số vấn đề phức tạp trở nên dễ giải quyết hơn. Hãy xem một ví dụ hơi phức tạp hơn: dãy Fibonacci.

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

for i in range(10):
print(fibonacci(i), end=" ")
# Output: 0 1 1 2 3 5 8 13 21 34

Hàm này tính toán số Fibonacci thứ n. Dãy Fibonacci bắt đầu với 0 và 1, và mỗi số tiếp theo là tổng của hai số trước nó.

Tìm Kiếm Nhị Phân Sử Dụng Đệ Quy

Bây giờ, hãy xử lý một ví dụ thực tế hơn: tìm kiếm nhị phân. Đây là một cách hiệu quả để tìm một mục trong danh sách sắp xếp.

def tim_kiem_nhi_phan(arr, low, high, x):
if high >= low:
mid = (high + low) // 2

if arr[mid] == x:
return mid
elif arr[mid] > x:
return tim_kiem_nhi_phan(arr, low, mid - 1, x)
else:
return tim_kiem_nhi_phan(arr, mid + 1, high, x)
else:
return -1

arr = [2, 3, 4, 10, 40]
x = 10

ket_qua = tim_kiem_nhi_phan(arr, 0, len(arr)-1, x)

if ket_qua != -1:
print(f"Phần tử có giá trị tại chỉ số {ket_qua}")
else:
print("Phần tử không có trong mảng")

Hàm này hoạt động bằng cách liên tục chia nhỏ khoảng tìm kiếm. Nếu giá trị của khóa tìm kiếm nhỏ hơn phần tử ở giữa khoảng, thu hẹp khoảng xuống phía dưới. Nếu không, thu hẹp khoảng lên phía trên. Liên tục kiểm tra cho đến khi tìm thấy giá trị hoặc khoảng trống.

Khi Nào Nên Sử Dụng Đệ Quy

Đệ quy đặc biệt hữu ích cho:

1. Các vấn đề có thể được chia nhỏ thành các vấn đề tương tự nhỏ hơn
2. Cấu trúc dữ liệu như cây (ví dụ: hệ thống tệp, HTML DOM)
3. Các thuật toán như QuickSort, MergeSort, v.v.

Tuy nhiên, đệ quy không luôn là giải pháp tốt nhất. Nó có thể tiêu thụ nhiều bộ nhớ cho các đệ quy sâu và đôi khi một vòng lặp đơn giản có thể hiệu quả và dễ hiểu hơn.

Bảng Phương Pháp Đệ Quy

Phương Pháp	Mô Tả	Ví Dụ
Đệ Quy Trực Tiếp	Hàm gọi chính nó một cách trực tiếp	Các ví dụ dem_nhay và giai_thua của chúng ta
Đệ Quy Gián Tiếp	Hàm A gọi hàm B, sau đó hàm B gọi lại hàm A	Xem ví dụ bên dưới
Đệ Quy Đuôi	Đệ quy cuối cùng là hàm được thực hiện	Ví dụ dem_nhay của chúng ta
Đệ Quy Không Đuôi	Đệ quy không phải là điều cuối cùng được thực hiện bởi hàm	Ví dụ giai_thua của chúng ta

Dưới đây là ví dụ về đệ quy gián tiếp:

def la_so_chan(n):
if n == 0:
return True
else:
return la_so_le(n - 1)

def la_so_le(n):
return not la_so_chan(n)

print(la_so_chan(4))  # Output: True
print(la_so_le(4))    # Output: False

Trong ví dụ này, la_so_chan gọi la_so_le, sau đó la_so_le gọi lại la_so_chan.

Kết Luận

Xin chúc mừng! Bạn đã bước ra những bước đầu tiên vào thế giới thú vị của đệ quy. Nhớ rằng, như bất kỳ công cụ mạnh mẽ nào, đệ quy nên được sử dụng một cách khôn ngoan. Nó có thể làm mã của bạn trở nên thanh lịch hơn và giải quyết các vấn đề phức tạp một cách dễ dàng, nhưng cũng có thể làm các vấn đề đơn giản trở nên không cần thiết phức tạp.

Khi bạn tiếp tục hành trình Python của mình, bạn sẽ gặp nhiều tình huống hơn nữa mà đệ quy có thể được áp dụng. Hãy tiếp tục tập luyện, và sớm bạn sẽ đệ quy như một chuyên gia!

Credits: Image by storyset