Hàm đệ quy trong Python

Trong các bài Python trước, bạn đã biết về hàm Python, các hàm Python tích hợp sẵn và hàm Python do người dùng định nghĩa. Trong bài này chúng ta sẽ tìm hiểu thêm về hàm đệ quy trong Python, hàm tự gọi chính nó, cũng như cách tạo hàm đệ quy và ví dụ minh họa.

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

Đệ quy là cách lập trình hoặc code một vấn đề, trong đó hàm tự gọi lại chính nó một hoặc nhiều lần trong khối code. Thông thường, nó trả giá trị trả về của lần gọi hàm. Nếu định nghĩa hàm thỏa mãn điều kiện đệ quy thì hàm được gọi là hàm đệ quy.

Đ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.

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.

Bài học đệ quy Python dừng lại tại đây. Trong bài tới, chúng ta sẽ tìm hiểu về hàm nặc danh/hàm Lambda trong Python, các bạn đừng bỏ lỡ nhé.

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