Hàm đệ quy trong Python

Đệ quy Python là kiến thức cơ bản mà mọi lập trình viên đều cần biết. Bài viết sẽ hướng dẫn bạn cách dùng đệ quy trong Python.

Hàm đệ quy trong Python là gì?

Đệ 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ỏ nó thành các bài toán con đơn giản hơn.

Trong Python, đệ quy đặc biệt hữu ích cho các bài toán có thể được chia thành các tác vụ nhỏ hơn giống hệt nhau, chẳng hạn như các phép tính toán học, duyệt cây hoặc thuật toán chia để trị.

Điều kiện chấm dứt: Một hàm đệ quy cần phải có điều kiện chấm dứt đề dừng việc tự gọi lại nó. Hàm đệ quy chấm dứt khi mỗi lần gọi đệ quy thì số giải pháp của vấn đề được giảm bớt và tiến gần đến điều kiện cơ sở. Một điều kiện cơ sở là điểm mà ở đó vấn đề được giải quyết và không cần đệ quy thêm. Nếu các lần gọi đệ quy không thể đến được điều kiện cơ sở thì hàm đệ quy trở thành một vòng lặp vô hạn.

Như vậy, có thể nói đệ quy trong khoa học máy tính là 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 đề đó.

Trong Python, hàm đệ quy cũng tương tự như vậy, có thể gọi đến chính nó và có một điều kiện cơ sở để chấm dứt đệ quy.

Đệ quy so với Lặp

• Đệ quy: Thường trực quan hơn và dễ triển khai hơn khi bài toán có tính đệ quy tự nhiên, chẳng hạn như duyệt cây. Nó có thể dẫn đến các giải pháp dễ hiểu hơn so với giải pháp lặp.
• Lặp: Lặp bao gồm các vòng lặp (for, while) để lặp lại việc thực thi một khối mã. Nhìn chung, nó tiết kiệm bộ nhớ hơn vì không liên quan đến nhiều khung ngăn xếp như đệ quy.

Khi nào nên tránh đệ quy

• Khi vấn đề có thể được giải quyết dễ dàng bằng vòng lặp.
• Khi độ sâu đệ quy đủ lớn để có nguy cơ tràn ngăn xếp.
• Khi hiệu suất là yếu tố quan trọng và chi phí gọi hàm là vấn đề.

Ví dụ về hàm đệ quy trong Python

Ví dụ kinh điển nhất về hàm đệ quy chính là tính giai thừa của một số nguyên. Giai thừa của một số là kết quả của phép nhân từ một đến số đó. Ví dụ, 5 giai thừa (được viết là 5!) là 1*2*3*4*5= 120.

Trong Python, hàm tính giai thừa của một số được viết như sau:

def giaithua(n):
    """Đây là hàm tính giai thừa của
    một số nguyên by Quantrimang.com"""
    if n == 1: 
       return 1 
    else: 
        return (n * giaithua(n-1))
num = 5
num1 = int(input("Nhập số cần tính giai thừa: "))
print("Giai thừa của", num, "là", giaithua(num)) 
print("Giai thừa của", num1, "là", giaithua(num1))

Trong ví dụ trên, bạn hãy nhìn vào phần định nghĩa hàm giaithua(n), trong lệnh if...else, hàm giaithua(n) đã gọi lại chính nó. Chạy code trên ta được kết quả sau:

Nhập số cần tính giai thừa: 9
Giai thừa của 5 là 120
Giai thừa của 9 là 362880

Khi gọi hàm giaithua(n) với số nguyên dương, nó sẽ gọi đệ quy bằng cách giảm dần số. Mỗi một lần gọi hàm, nó sẽ nhân số với giai thừa của 1 cho đến khi số bằng 1. Việc gọi đệ quy này có thể được giải thích trong các bước sau:

giaithua(4)             # Lần gọi đầu tiên với 4
4 * giaithua(3)         # Lần gọi thứ hai với 3
4 * 3 * giaithua(2)     # Lần gọi thứ ba với 2
4 * 3 * 2 * giaithua(1) # Lần gọi thứ tư với 1
4 * 3 * 2 * 1           # Trả về từ lần gọi 4 khi số =1
4 * 3 * 2               # Trả về từ lần gọi 3
4 * 6                   # Trả về từ lần gọi 2
24                      # Trả về từ lần gọi 1

Phép đệ quy trên kết thúc khi số giảm xuống đến 1. Đây được gọi là điều kiện cơ sở. Mỗi hàm đệ quy phải có một điều kiện cơ sở để dừng việc đệ quy nếu không nó sẽ trở thành hàm vô hạn, tự gọi mãi đến nó.

Ưu/Nhược điểm của hàm đệ quy

Mỗi một lần hàm đệ quy tự gọi nó sẽ lưu trữ trên bộ nhớ. Vì thế, nó tiêu tốn nhiều bộ nhớ hơn so với hàm truyền thống. Python sẽ dừng gọi hàm sau 1000 lần gọi. Nếu bạn chạy code dưới đây:

def giaithua(n):
    """Đây là hàm tính giai thừa của
    một số nguyên by Quantrimang.com"""
    if n == 1: 
       return 1 
    else: 
       return (n * giaithua(n-1))

print (giaithua(1001))

Sẽ nhận được thông báo lỗi:

RecursionError: maximum recursion depth exceeded in comparison

Có thể giải quyết vấn đề này bằng cách điều chỉnh số lần gọi đệ quy, như sau:

import sys
sys.setrecursionlimit(5000)

def giaithua(n):
    """Đây là hàm tính giai thừa của
    một số nguyên by Quantrimang.com"""
    if n == 1: 
       return 1 
    else: 
       return (n * giaithua(n-1))

print (giaithua(1001))

Nhưng nhớ rằng, vẫn còn có giới hạn đầu vào cho hàm giai thừa. Vì lý do này, bạn nên sử dụng đệ quy một cách khôn ngoan. Để tính giai thừa thì đệ quy không phải là giải pháp tốt nhất, đối với các vấn đề khác như di chuyển trong thư mục (traversing a directory) thì đệ quy là một giải pháp tốt.

Đệ quy là một khái niệm mạnh mẽ trong Python, giúp giải quyết các vấn đề phức tạp bằng cách chia nhỏ chúng thành các bài toán con đơn giản hơn. Khi được sử dụng đúng cách, đệ quy tạo ra mã lệnh rõ ràng, súc tích và dễ hiểu.

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

Mặc dù đôi khi đệ quy có thể kém hiệu quả hơn phép lặp, nhưng nó là một công cụ vô giá để giải quyết một số loại vấn đề nhất định, đặc biệt là những vấn đề liên quan đến dữ liệu phân cấp hoặc vốn dĩ có thể giải quyết bằng đệ quy.

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

Trên đây là những điều bạn cần biết về hàm đệ quy trong Python. Hi vọng bài viết hữu ích với các bạn.

Bạn đừng quên kho bài tập Python của Quantrimang.com nhé.