Đệ quy — Cách hoạt động, ví dụ và trường hợp cơ sở

Trong toán học, đệ quy là cách định nghĩa một hàm, dãy số hoặc quá trình bằng các trường hợp nhỏ hơn của cùng một ý tưởng. Một định nghĩa đệ quy chỉ hoạt động nếu nó có trường hợp cơ sở và một quy tắc đưa mỗi trường hợp mới tiến dần về trường hợp cơ sở đó.

Nếu bạn chỉ cần ý chính, thì là thế này: đệ quy sẽ không còn hữu ích ngay khi quy tắc “bước nhỏ hơn” không còn dẫn đến một điểm dừng hợp lệ.

Đệ quy trong toán học có nghĩa là gì

Một định nghĩa đệ quy không liệt kê riêng từng trường hợp. Thay vào đó, nó cho một điểm bắt đầu và một quy tắc để xây dựng các trường hợp lớn hơn từ các trường hợp nhỏ hơn.

Điều đó khác với công thức tường minh. Công thức tường minh cho đáp án từ đầu vào chỉ bằng một biểu thức. Còn định nghĩa đệ quy rút bài toán từng bước cho đến khi chạm tới một trường hợp đã biết.

Vì sao cần có trường hợp cơ sở

Trường hợp cơ sở là điểm dừng. Nếu không có nó, định nghĩa sẽ cứ tiếp tục tham chiếu đến các trường hợp ngày càng nhỏ hơn mà không bao giờ kết thúc.

Trường hợp cơ sở cũng phải phù hợp với quy tắc bạn chọn. Nếu bước đệ quy giảm từ $n$ xuống $n-1$, thì trường hợp cơ sở phải có thể đạt tới theo mẫu đó với các đầu vào được phép.

Ví dụ chi tiết: đệ quy của giai thừa

Giai thừa là một định nghĩa đệ quy tiêu chuẩn. Với các số nguyên không âm $n \ge 0$, định nghĩa giai thừa bởi

$$0! = 1$$

và, với $n \ge 1$,

$$n! = n(n-1)!$$

Ở đây, $0! = 1$ là trường hợp cơ sở, còn $n! = n(n-1)!$ là bước đệ quy.

Để tìm $4!$, ta tiếp tục rút gọn cho đến khi xuất hiện trường hợp cơ sở:

$$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 0!$$

Bây giờ áp dụng trường hợp cơ sở $0! = 1$:

$$4! = 4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$$

Đó là toàn bộ mẫu đệ quy: rút về trường hợp nhỏ hơn, chạm trường hợp cơ sở, rồi tính ngược trở lại câu hỏi ban đầu.

Đệ quy và hệ thức truy hồi

Đệ quy là ý tưởng rộng hơn. Hệ thức truy hồi là một quy tắc đệ quy cho một dãy số, trong đó mỗi số hạng phụ thuộc vào các số hạng trước đó.

Ví dụ, dãy Fibonacci được cho bởi một hệ thức truy hồi vì mỗi số hạng được xác định từ các số hạng trước. Giai thừa cũng là đệ quy, nhưng thường được trình bày như một định nghĩa đệ quy của hàm hơn là một hệ thức truy hồi cho dãy số.

Những lỗi đệ quy thường gặp

Bỏ quên trường hợp cơ sở

Nếu không có trường hợp cơ sở, định nghĩa sẽ không kết thúc.

Dùng một bước không làm bài toán nhỏ đi

Nếu bước đệ quy không tiến về phía trường hợp cơ sở, quá trình có thể lặp vô hạn hoặc trở nên không xác định với một số đầu vào.

Quên điều kiện áp dụng của quy tắc

Trong ví dụ giai thừa, quy tắc $n! = n(n-1)!$ được dùng cho $n \ge 1$. Điều kiện đó rất quan trọng. Nếu thiếu nó, bạn có thể cố áp dụng quy tắc ở nơi mà định nghĩa không hề được dự định dùng tới.

Cho rằng đệ quy chỉ là ý tưởng trong lập trình

Đệ quy xuất hiện trong toán học từ rất lâu trước khi có mã lệnh. Nó là một cách định nghĩa hàm, dãy số và tập hợp bằng cách tham chiếu đến các trường hợp nhỏ hơn. Sau đó, quy nạp thường được dùng để chứng minh các mệnh đề về những định nghĩa đệ quy đó.

Khi nào đệ quy hữu ích

Đệ quy hữu ích khi một bài toán tự nhiên tách thành các phiên bản nhỏ hơn của chính nó. Bạn sẽ thấy nó trong giai thừa, các dãy kiểu Fibonacci, các tập được định nghĩa đệ quy và nhiều thuật toán.

Nó đặc biệt hữu ích khi trường hợp nhỏ hơn có cùng cấu trúc với trường hợp ban đầu. Nếu trường hợp nhỏ hơn thực ra không phải cùng một kiểu bài toán, thì đệ quy thường không phải là công cụ phù hợp.

Một bài kiểm tra nhanh cho một định nghĩa đệ quy chặt chẽ

Hãy tự hỏi hai câu:

1. Tôi có trường hợp cơ sở không?
2. Mỗi bước đệ quy có tiến gần hơn đến nó không?

Nếu một trong hai câu trả lời là không, thì định nghĩa đó cần được sửa.

Thử một bài tương tự

Định nghĩa một dãy số bởi

$$a_1 = 2, \qquad a_n = a_{n-1} + 3 \quad \text{for } n \ge 2$$

Sau đó tìm $a_2$, $a_3$ và $a_4$. Đây là cách nhanh để luyện nhận ra trường hợp cơ sở và bước đệ quy trong một bối cảnh mới.