Đệ quy trong Python

Đệ quy liên quan đến một hàm gọi chính nó trực tiếp hoặc gián tiếp để giải quyết vấn đề bằng cách chia nhỏ thành các phần đơn giản hơn và dễ quản lý hơn. Trong Python , đệ quy được sử dụng rộng rãi cho các tác vụ có thể được chia thành các tác vụ con giống hệt nhau.

Trong Python, một hàm đệ quy được định nghĩa giống như bất kỳ hàm nào khác , nhưng nó bao gồm một lệnh gọi đến chính nó. Cú pháp và cấu trúc của một hàm đệ quy tuân theo định nghĩa hàm thông thường trong Python, với việc bổ sung một hoặc nhiều điều kiện dẫn đến hàm gọi chính nó.

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

print(factorial(5))

Đầu ra:

120

Giải thích: Giai thừa của một số n (ký hiệu là n!) là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng n. Phương pháp đệ quy liên quan đến hàm tự gọi với giá trị giảm dần của n cho đến khi đạt đến trường hợp cơ sở là 1.

Hãy cùng tìm hiểu sâu hơn về đệ quy trong Python:

Cấu trúc cơ bản của hàm đệ quy

def hàm đệ quy(tham số):

    nếu điều kiện trường hợp cơ sở:

        trả về kết quả cơ sở

    khác:

        trả về hàm đệ quy(tham số đã sửa đổi)

Trường hợp cơ sở và trường hợp đệ quy

• Trường hợp cơ sở: Đây là điều kiện mà đệ quy dừng lại. Điều quan trọng là ngăn chặn các vòng lặp vô hạn và đảm bảo rằng mỗi lệnh gọi đệ quy làm giảm vấn đề theo một cách nào đó. Trong ví dụ giai thừa, trường hợp cơ sở là n == 1.

• Trường hợp đệ quy: Đây là phần của hàm bao gồm lệnh gọi đến chính nó. Cuối cùng nó phải dẫn đến trường hợp cơ sở. Trong ví dụ giai thừa, trường hợp đệ quy là return n * factorial(n-1).

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

print(fibonacci(10))

Đầu ra:

55

Giải thích:

• Trường hợp cơ bản: Nếu n 0, hàm trả về 0. Nếu n 1, hàm trả về 1. Hai trường hợp này là cần thiết để dừng đệ quy.

• Trường hợp đệ quy: Hàm tự gọi chính nó hai lần với các lần giảm n (tức là fibonacci(n-1) và fibonacci(n-2)), tổng hợp kết quả của các lần gọi này. Việc chia thành các bài toán con nhỏ hơn tiếp tục cho đến khi đạt đến các trường hợp cơ sở.

Các loại đệ quy trong Python

Đệ quy có thể được phân loại thành hai loại: đệ quy đuôi và đệ quy không đuôi. Sự khác biệt chính giữa chúng liên quan đến những gì xảy ra sau lệnh gọi đệ quy.

• Đệ quy đuôi : Điều này xảy ra khi lệnh gọi đệ quy là thao tác cuối cùng được thực thi trong hàm, không có công việc hoặc phép tính bổ sung nào sau lệnh gọi đệ quy. Trong nhiều ngôn ngữ lập trình, đệ quy đuôi có thể được trình biên dịch tối ưu hóa thành các vòng lặp lặp để cải thiện hiệu suất và ngăn chặn tràn ngăn xếp.

• Đệ quy không đuôi : Điều này xảy ra khi có các hoạt động hoặc tính toán theo sau lệnh gọi đệ quy. Kiểu này ngăn trình biên dịch hoặc trình thông dịch tối ưu hóa đệ quy thành một lần lặp.

Sau đây là một ví dụ Python minh họa cả đệ quy đuôi và đệ quy không đuôi:

def tail_fact(n, acc=1):
    # Trường hợp cơ sở
    if n == 0:
        return acc
    # Gọi đệ quy đuôi với một biến tích lũy
    else:
        return tail_fact(n - 1, acc * n)

def nontail_fact(n):
    # Trường hợp cơ sở
    if n == 1:
        return 1
    # Gọi đệ quy không đuôi vì phép nhân xảy ra sau lời gọi hàm
    else:
        return n * nontail_fact(n - 1)

# Ví dụ sử dụng
print(tail_fact(5))       # Kết quả: 120
print(nontail_fact(5))    # Kết quả: 120

Đầu ra:

120 
120

Đệ quy so với Lặp lại

Đệ quy:

• Đệ quy thường trực quan hơn và dễ triển khai hơn khi vấn đề có tính đệ quy tự nhiên, như duyệt cây.

• Nó có thể đưa đến những giải pháp dễ hiểu hơn so với những giải pháp lặp đi lặp lại.

Lặp lại:

• Lặp lại 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, phương pháp này tiết kiệm bộ nhớ hơn vì không liên quan đến nhiều khung ngăn xếp như đệ quy.

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

• Tính đơn giản: Mã đệ quy thường đơn giản và rõ ràng hơn, đặc biệt đối với các vấn đề vốn có tính đệ quy (ví dụ: duyệt cây, các vấn đề lập trình động).

• Giảm độ dài mã: Đệ quy có thể giảm độ dài của mã vì các tác vụ lặp đi lặp lại được xử lý thông qua các lệnh gọi hàm lặp đi lặp lại.

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

• Chi phí bộ nhớ: Mỗi lệnh gọi đệ quy sẽ thêm một lớp mới vào ngăn xếp, điều này có thể dẫn đến sử dụng bộ nhớ đáng kể, đặc biệt là đối với đệ quy sâu.

• Các vấn đề về hiệu suất: Các hàm đệ quy có thể dẫn đến phản hồi chậm hơn do các chi phí chung như gọi hàm và trả về.

• Nguy cơ tràn ngăn xếp: Đệ quy quá mức có thể dẫn đến lỗi tràn ngăn xếp nếu độ sâu đệ quy vượt quá giới hạn ngăn xếp.