Hàm đệ Quy Trong Python | Lập Trình Từ Đầu

1. Định nghĩa hàm đệ quy trong Python

Trong khi sử dụng và khai báo một hàm trong Python, ta biết rằng một hàm có thể gọi các hàm khác. Ngoài ra, các hàm còn có thể tự gọi chính nó. Việc một hàm có sự gọi lại chính nó ở bên trong hàm được gọi là hàm đệ quy.

Ảnh dưới đây, miêu tả một cấu trúc của hàm đệ quy trong Python:

Trong ảnh trên ta thấy hàm recurse() được khai báo và thực hiện gọi lại chính hàm recurse(). Nếu như bắt gặp cách gọi hàm như vậy, chúng ta sẽ nhận dạng luôn hàm recurse() là một hàm đệ quy.

Một hàm đệ quy trong Python gồm 2 phần

• Phần cơ sở:  Là việc khai báo một điều kiện dừng để kết thúc việc gọi đệ quy cho hàm. Nếu các lần gọi đệ quy trong hàm không tồn tại một điều kiện kết thúc sẽ gây ra việc hàm đệ quy trở thành một vòng lặp vô hạn.
• Phần đệ quy: Là phần thân của hàm có chứa phần gọi đệ quy, thực hiện cho đến khi thỏa mãn điều kiện ở phần cơ sở.

Trong khoa học máy tính (hay lập trình máy tính), đệ quy một phương pháp giải quyết vấn đề dựa trên việc giải quyết các trường hợp nhỏ hơn của cùng vấn đề đó.

2. Ví dụ hàm đệ quy trong Python

2.1 Tính giai thừa của một số sử dụng đệ quy trong Python

Ví dụ đơn giản và dễ hiểu nhất khi mới tiếp cận với hàm đệ quy đó là việc áp dụng hàm đệ quy để tính ra kết quả giai thừa của một số n.

Như ta đa biết, n! (n giai thừa) được tính theo công thức n! = n * (n-1)! –  ta có thể sử dụng công thức này làm phần đệ quy – chính là phần được gọi lại trong hàm.

Khi tính giai thừa của một số người ta quy ước 0! = 1 và 1! = 1 ta có thể dùng quy ước này làm phần cơ sở của hàm đệ quy (điều kiện dừng của hàm đệ quy)

Hàm tính giai thừa của một số n trong Python sẽ như sau:

def giaithua(n): # Neu n = 1 if n == 1: # Ket thuc ham de quy va return 1 return 1 else: # Truong hop n chua bang 1 return (n * giaithua(n-1)) # Goi lai de quy giai thua theo cong thuc n * (n-1)! # Khai bao n n = 5 # Goi ham giai thua voi n = 5 ketqua = giaithua(n) # Hien thi ket qua print("Ket qua tinh giai thua la: {0}".format(ketqua))

Kết quả:

Ket qua tinh giai thua la: 120

Giải thích:

• Khi gọi hàm giaithua(n) và truyền vào đối số n cần tính giai thừa vào hàm, nó sẽ gọi đệ quy bằng cách giảm dần số n sau mỗi lần gọi hàm. Trong trường hợp số n vẫn lớn hơn 1, hàm sẽ thực hiện phần đệ quy bằng cách sử dụng theo công thức n * (n-1)!
• Hàm đệ quy trên kết thúc khi n giảm xuống đến 1 – đến lúc này chính phần cơ sở của hàm đệ quy máy tính sẽ thực hiện giải đệ quy ngược lại từ điều kiện n = 1 cho đến n = 5

Ta có thể hình dung rõ hơn việc gọi đệ quy và giải đệ quy của hàm tính giai thừa như sau:

# Goi de quy tinh giai thua voi 5 lan goi giaithua(5) = 5 * giaithua(4) giaithua(4) = 4 * giaithua(3) giaithua(3) = 3 * giaithua(2) giaithua(2) = 2 * giaithua(1) giaithua(1) = 1 # Sau khi n = 1 thuc hien giai de quy tu 1 den 5 giaithua(5) = 5 * giaithua(4) = 5 * 24 = 120 giaithua(4) = 4 * giaithua(3) = 4 * 6 = 24 giaithua(3) = 3 * giaithua(2) = 3 * 2 = 6 giaithua(2) = 2 * giaithua(1) = 2 * 1 = 2 giaithua(1) = 1 # n = 1 => return 1

2.2 Duyệt List trong Python bằng đệ quy

Ta cũng có thể sử dụng đệ quy trong Python như một phương pháp lặp. Khi đó ta sẽ gọi lại hàm đệ quy để duyệt qua các phần tử có trong một List, Tuple, Set….

Ví dụ minh hoạ dưới đây, sử dụng hàm đệ quy để duyệt qua một list trong Python. Lưu ý rằng, trong Python các phần tử trong một List bắt đầu từ chỉ mục 0, và phần tử cuối cùng trong List ở chỉ mục n – 1. Ví dụ dưới đây sẽ duyệt một list trong python từ phần tử cuối (n -1) về phần tử đầu tiên (0) trong List.

# Khai bao list gom 5 phan tu listA = [1, 2, 3, 4, 5] # Khai bao ham duyet list su dung de quy def loopList(n): # Hien thi phan tu listA[n] print(listA[n]) if (n == 0): # Neu n = 0 return 0 # Ket thuc viec duyet cac phan tu trong listA else: # Truong hop n chua bang 0 loopList(n-1) # Tiep tuc duyet listA voi phan tu n - 1 # Khai bao so luong chi muc co trong listA n = len(listA) - 1 # Duyet listA tu phan tu listA[n], listA[n-1], listA[n-2]....listA[0] loopList(n)

Kết quả:

5 4 3 2 1

Việc duyệt một list bằng hàm đệ quy ở trên sẽ được làm tương tự với vòng lặp for bên dưới đây:

# Khai bao list gom 5 phan tu listA = [1, 2, 3, 4, 5] # Duyet list bang vong lap for for x in listA[::-1]: # listA[::-1] la viec dao nguoc phan tu trong list # Hien thi cac phan tu x sau khi duyet print(x)

Kết quả:

5 4 3 2 1

So sánh ở hai chương trình trên, ta nhận thấy rằng phương pháp lặp bằng vòng lặp for cho thấy sự tối ưu hoá hơn về các đoạn mã. Ngoài ra, số lượng tính toán sẽ tăng gấp đôi trên mỗi lần gọi đệ quy, vì vậy khi cần duyệt một list với quá nhiều phần tử chương trình sẽ cần phải tốn một lượng thời gian để tính toán đưa ra kết quả!

3. Ưu nhược điểm của đệ quy trong Python

Ưu điểm của việc sử dụng đệ quy

• Một hàm phức tạp có thể được chia thành các bài toán con nhỏ hơn bằng cách sử dụng đệ quy.
• Có thể tạo một chuỗi đơn giản hơn thông qua đệ quy
• Giải quyết một số bài toán về đồ thị, cấu trúc cây…

Nhược điểm của việc sử dụng đệ quy

• Rất nhiều bộ nhớ và thời gian được sử dụng thông qua các lần gọi đệ quy, gây tốn kém cho việc sử dụng.
• Các hàm đệ quy rất khó gỡ lỗi.
• Hàm đệ quy gây khó hiểu cho người đọc