Sức mạnh của đệ quy trong lập trình

Hình ảnh: Tam giác Sierpinski

Trong lĩnh vực lập trình, đệ quy là một phương pháp mạnh mẽ khi một hàm gọi lại chính nó. Đây là một khái niệm quan trọng trong toán học và khoa học máy tính. Hãy cùng tìm hiểu về sức mạnh của đệ quy và cách nó ứng dụng trong lập trình.

Khái niệm về đệ quy

Trong toán học và khoa học máy tính, ta nói một tính chất hoặc cấu trúc là đệ quy nếu nó được xác định bằng cách xác định một số trường hợp đơn giản và sau đó áp dụng quy tắc để chuyển các trường hợp phức tạp thành các trường hợp đơn giản.

Ví dụ, quan hệ tổ tiên được định nghĩa đệ quy như sau:

• Bố mẹ của một người là tổ tiên của người đó (trường hợp cơ bản).
• Bố mẹ của tổ tiên của một người bất kỳ cũng là tổ tiên của người đó (bước đệ quy).

Các định nghĩa đệ quy tương tự cũng được sử dụng trong toán học.

Định nghĩa theo đệ quy

Một khái niệm X được định nghĩa theo đệ quy nếu nó sử dụng chính khái niệm X trong định nghĩa của nó.

Ví dụ 1: Định nghĩa số tự nhiên

• 0 được coi là một số tự nhiên.
• n được coi là số tự nhiên nếu n - 1 cũng là số tự nhiên.

Ứng dụng của đệ quy trong khoa học máy tính

Đệ quy là một phương pháp quan trọng để giải quyết các bài toán phức tạp bằng cách chia chúng thành các bài toán con đơn giản hơn. Phương pháp này được gọi là Thuật toán chia để trị và là cơ sở của quy hoạch động.

Một ví dụ cổ điển của đệ quy là hàm giai thừa được viết bằng ngôn ngữ C hoặc C++ như sau:

int giaiThua(int n)
{
    if (n == 0)
        return 1;
    else
        return n * giaiThua(n - 1);
}

Một ví dụ khác về đệ quy là thủ tục duyệt tất cả các nút của một cấu trúc dữ liệu cây:

void duyetCay(node *root)
{
    if (root != NULL)
    {
        // Thực hiện công việc trên nút gốc
        duyetCay(root->left); // Duyệt cây con trái
        duyetCay(root->right); // Duyệt cây con phải
    }
}

Cấu trúc cây cũng được định nghĩa bằng đệ quy. Mỗi nút chứa một danh sách các nút con của nó.

Ví dụ về chương trình đệ quy

Trong lập trình, một chương trình con được gọi là đệ quy nếu nó gọi lại chính nó trong quá trình thực thi.

Cấu trúc chương trình con đệ quy gồm hai phần:

• Phần cơ sở: chứa tác động của chương trình con với các giá trị ban đầu của tham số.
• Phần đệ quy: định nghĩa các tác động tiếp theo cho giá trị hiện tại của tham số bằng cách sử dụng các tác động đã được xác định trước đó với các tham số nhỏ hơn.

Ví dụ: Hàm tính giai thừa của một số tự nhiên n (ký hiệu n!). Dưới đây là một đoạn mã viết bằng ngôn ngữ Pascal:

function giaiThua(n: integer): integer;
begin
    if n = 0 then
        giaiThua := 1
    else
        giaiThua := n * giaiThua(n - 1);
end;

Kết quả của một chương trình đệ quy được thực hiện như sau:

• Khi gọi hàm giaiThua(3), máy tính ghi nhớ n = 3 và tính giaiThua(2).
• Tiếp theo, máy tính ghi nhớ n = 2 và tính giaiThua(1).
• Theo định nghĩa hàm, máy tính trả về 1.
• Tiếp tục tính toán, máy tính trả về 2 * 1 = 2.
• Cuối cùng, máy tính trả về 3 * 2 = 6.
• Vậy kết quả của giaiThua(3) là 6.

Đệ quy tương hỗ

Nếu hai chương trình con A1 và A2 gọi lẫn nhau, ta có đệ quy tương hỗ.

Đệ quy tương hỗ thường được sử dụng để duyệt cây theo chiều sâu.

Kết luận

Đệ quy là một phương pháp mạnh mẽ trong lập trình, cho phép giải quyết các bài toán phức tạp bằng cách chia chúng thành các bài toán con đơn giản hơn. Đây là một khái niệm quan trọng trong toán học và khoa học máy tính. Việc sử dụng đệ quy tương hỗ và quy hoạch động cũng giúp tối ưu hóa các thuật toán và giải quyết các bài toán khó khăn.

Xem thêm:

• Thuật toán quay lui
• Quy nạp toán học
• Tháp Hà Nội

Tham khảo: