Trong cuộc sống, chúng ta đôi khi bắt gặp những hình ảnh về một vật mà chứa bên trong nó là một vật khác giống hệt nó, như búp bê Matryoska, cửa sổ OBS khi bạn cố dùng nó để quay màn hình của chính nó, sách giáo khoa Toán lớp 3 cũ, link này, … Tương tự như vậy, trong khoa học máy tính và lập trình, chúng ta xây dựng khái niệm về đệ quy.
Đệ quy và giải thuật đệ quy
Khái niệm
Ta gọi một đối tượng là đệ quy [recursion] nếu nó được định nghĩa qua chính nó hoặc một đối tượng cùng dạng với chính nó bằng quy nạp.
Ví dụ:
- Với $n!$ thì ta có $n! = [n - 1]! \times n$
- Gọi $gcd[a, b]$ là ước chung lớn nhất của $a$ và $b$ [$a \geq b$] thì ta có $gcd[a, b] = gcd[b, a \bmod b]$ với $\bmod$ là phép lấy phần dư
Nếu một bài toán $P$ có lời giải được thực hiện bằng một bài toán con $P'$ có dạng giống $P$ thì đó là một giải thuật đệ quy. Ở đây, $P'$ cần là một bài toán đơn giản hơn $P$ [có kích cỡ dữ liệu nhỏ hơn, hoặc độ phức tạp nhỏ hơn, …], và đương nhiên không cần đến $P$ để giải nó.
Về cơ bản thì ta có thể gọi một hàm là đệ quy nếu hàm đó tự gọi chính nó, với các biến đầu vào có thể khác.
Một bài toán đệ quy có lời giải gồm 2 phần:
- Phần neo/trường hợp cơ sở [anchor/base case]: Đây là phần có thể giải trực tiếp mà không cần phải dựa vào một bài toán con nào, và cũng chính là điểm dừng của lời giải đệ quy. Phần này thường là các trường hợp cụ thể, như
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2;0,
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2; - Phần đệ quy: Đây chính là phần mà bạn phải gọi ra bài toán con và giải nó, cũng chính là gọi hàm đệ quy. Phần này sẽ được thực hiện đến khi nào bài toán đưa được về trường hợp cơ sở.
Nếu ta đem so sánh với con Matryoska, thì trường hợp cơ sở là con bé nhất ở trong cùng, còn đệ quy chính là thực hiện việc mở một con to liên tục đến lúc nào không thể mở được nữa.
Lý thuyết suông thì quá khó hiểu, hãy cùng xem một số ví dụ:
Tính giai thừa
Bài toán: Cho số tự nhiên $n$ [$n \leq 15$]. Tính $n!$
Phân tích: Ở phần trên, chúng ta đã tìm được công thức đệ quy của bài toán này: $n! = [n - 1]! \times n$. Khi lập trình đệ quy, cơ bản thuật toán sẽ hoạt động như sau với $n = 2$: để tính $2!$, chúng ta phải tính nó qua $1!$; để tính $1!$ chúng ta phải tính $0!$. Lúc này, ta có hai lựa chọn:
- Tiếp tục với $0! = [-1]! \times 0$
- Thay $0! = 1$ vào và tính tiếp
Lựa chọn thứ nhất có vẻ không khả thi, phần vì $[-1]!$ không xác định, mặt khác nếu thay tiếp thì chúng ta cũng chẳng biết dừng ở đâu cả. Với $0! = 1$, ta có thể thay vào để tính $1!$ rồi. Có $1!$ ta lại thay nó vào tiếp để tính $2!$, và chúng ta có thứ chúng ta cần.
Phân tích thì dài dòng vậy thôi, còn cài đặt thì rất đơn giản:
void factorial[int n]
{
if [n == 0] return 1; //trường hợp cơ sở
return factorial[n - 1] * n; //phần đệ quy
}Nếu bạn chưa quen với cú pháp đệ quy như vậy thì có thể hiểu hàm trên tương đương với hàm
//n = 0
void factorial_0[]
{
return 1;
}
//n = 1
void factorial_1[]
{
return factorial_0[] * 1;
}
//n = 2
void factorial_2[]
{
return factorial_1[] * 2;
}2 trong đoạn code sau với $n = 2$:
//n = 0
void factorial_0[]
{
return 1;
}
//n = 1
void factorial_1[]
{
return factorial_0[] * 1;
}
//n = 2
void factorial_2[]
{
return factorial_1[] * 2;
}Tính số Fibonacci
Dãy Fibonacci là dãy số được định nghĩa theo công thức truy hồi sau:$f_n = \begin{cases} 0 & \text{với } n = 0\\ 1 & \text{với } n = 1\\ f_{n - 2} + f_{n - 1} & \text{với } n > 1 \end{cases}$Văn vẻ hơn thì trong dãy này, mỗi số hạng bằng tổng của hai số hạng liền trước nó. Các giá trị $f_0$, $f_1$ có thể khác một chút tuỳ tài liệu.
Bài toán: Tìm số Fibonacci thứ $n$ [$n \leq 20$].
Dựa vào công thức truy hồi đã cho và lập luận kiểu "để tính $f$ này thì ta cần có $f$ kia" như trên, chúng ta có thể cài đặt như sau:
void fibo[int n]
{
if [n == 0] return 0; //trường hợp cơ sở
if [n == 1] return 1; //trường hợp cơ sở
return fibo[n - 2] + fibo[n - 1]; //phần đệ quy
}Cần chú ý rằng ở chương trình này cần có tới 2 trường hợp cơ sở, vì đó cũng là hai trường hợp không thể áp dụng công thức truy hồi.
Mở rộng: Hãy thử sử dụng phương pháp này để cài đặt một chương trình đệ quy tính ƯCLN dựa vào công thức ở ví dụ phía trên.
Đương nhiên, không phải bài toán đệ quy nào cũng để chúng ta nhìn thấy một công thức đệ quy đơn giản như vậy. Thậm chí, đôi khi chúng ta còn chẳng có một công thức cụ thể, mà chỉ đơn thuần là công việc được thực hiện sau đó có điểm tương đồng với phần trước thôi. Lúc này, ta cần giải đáp những câu hỏi:
- Bài toán có thể được giải qua những bài toán con nào tương tự không? Nếu được, đó là gì?
- Tới trạng thái nào, chúng ta sẽ dừng lại?
Thuật toán quay lui
Khái niệm
Thuật toán quay lui [backtracking] dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.
Tóm gọn lại, chúng ta đang xây dựng một danh sách gồm tất cả các tập hợp [hay dãy, …], mà mỗi phần tử được xét tất cả các trường hợp có thể của nó. Phương pháp này cũng gọi là duyệt vét cạn.
Để cho khỏi "lú", trong bài viết này chúng ta thống nhất sẽ dùng cụm từ danh sách các tập hợp/dãy/xâu.
Ví dụ: khi tìm danh sách các dãy nhị phân [các dãy gồm toàn các ký tự $0$, $1$ như dãy $0001011$] độ dài $3$, ta sẽ:
- Xét mọi trường hợp ký tự thứ nhất. Ta được
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2;3 hoặc
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2; - Với mỗi trường hợp của ký tự thứ nhất, xét tiếp mọi trường hợp ký tự thứ hai. Ta được
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2;5,
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2;6 từ
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2;3 ở bước trước và
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2;8,
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2;9 từ
//n = 0 void factorial_0[] {
} //n = 1 void factorial_1[] {return 1;
} //n = 2 void factorial_2[] {return factorial_0[] 1;
}return factorial_1[] 2; - Tương tự, với mỗi trường hợp của ký tự thứ hai, ta xét nốt mọi trường hợp ở ký tự thứ ba. Các dãy nhận được là
void fibo[int n] {
}if [n == 0] return 0; //trường hợp cơ sở if [n == 1] return 1; //trường hợp cơ sở return fibo[n - 2] + fibo[n - 1]; //phần đệ quy1,
void fibo[int n] {
}if [n == 0] return 0; //trường hợp cơ sở if [n == 1] return 1; //trường hợp cơ sở return fibo[n - 2] + fibo[n - 1]; //phần đệ quy2,
void fibo[int n] {
}if [n == 0] return 0; //trường hợp cơ sở if [n == 1] return 1; //trường hợp cơ sở return fibo[n - 2] + fibo[n - 1]; //phần đệ quy3,
void fibo[int n] {
}if [n == 0] return 0; //trường hợp cơ sở if [n == 1] return 1; //trường hợp cơ sở return fibo[n - 2] + fibo[n - 1]; //phần đệ quy4,
void fibo[int n] {
}if [n == 0] return 0; //trường hợp cơ sở if [n == 1] return 1; //trường hợp cơ sở return fibo[n - 2] + fibo[n - 1]; //phần đệ quy5,
void fibo[int n] {
}if [n == 0] return 0; //trường hợp cơ sở if [n == 1] return 1; //trường hợp cơ sở return fibo[n - 2] + fibo[n - 1]; //phần đệ quy6,
void fibo[int n] {
}if [n == 0] return 0; //trường hợp cơ sở if [n == 1] return 1; //trường hợp cơ sở return fibo[n - 2] + fibo[n - 1]; //phần đệ quy7,
void fibo[int n] {
}if [n == 0] return 0; //trường hợp cơ sở if [n == 1] return 1; //trường hợp cơ sở return fibo[n - 2] + fibo[n - 1]; //phần đệ quy
Trên phương diện quy nạp, nếu cần dựng danh sách các tập hợp mà mỗi tập có dạng ${x_1, x_2, …, x_n}$, ta xét mọi giá trị của $x_1$, rồi sau đó duyệt tiếp ${x_2, x_3, …, x_n}$, tiếp tục xét mọi giá trị $x_2$, rồi lại duyệt ${x_3, x_4, …, x_n}$, …, cho đến khi nào tất cả các giá trị đều đã xác định. Lúc này, ta lưu tập vừa tạo lại vào danh sách và tiếp tục chuyển sang tập khác từ các giá trị khác của các $x_i$
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}Việc thêm giá trị mới vào tập đang xét rồi cuối cùng xoá bỏ nó ra khỏi tập giải thích cho tên gọi "quay lui" của thuật toán. Đó là việc khôi phục lại trạng thái cũ của tập hợp sau khi kết thúc việc gọi đệ quy.
Bạn đọc có thể thử vẽ sơ đồ tính toán giống như bài giai thừa ở trên và quen sát xem các hàm đệ quy được gọi ra theo thứ tự như thế nào.
Bạn vừa tiếp thu một lượng khá lớn kiến thức, và có thể sẽ gặp chút vấn đề. Không sao, chúng ta hãy đi vào ví dụ để hiểu hơn.
Sinh các dãy nhị phân
Bài toán: Liệt kê tất cả các dãy nhị phân độ dài $n$, là dãy có tất cả $n$ ký tự và gồm toàn các ký tự $0$ và $1$. Ví dụ, với $n = 3$ ta có các dãy $000, 001, 010, 011, 100, 101, 110, 111$.
Phân tích: Ở ví dụ phía trên, chúng ta đã nói về việc xét mọi trường hợp để xây dựng các dãy này như thế nào. Khi cài đặt đệ quy, sử dụng tư duy quy nạp "xây tập sau từ tập trước", thuật toán sẽ hoạt động như sau:
Tại hàm
void fibo[int n]
{
if [n == 0] return 0; //trường hợp cơ sở
if [n == 1] return 1; //trường hợp cơ sở
return fibo[n - 2] + fibo[n - 1]; //phần đệ quy
}9, ta xét từng giá trị của ký tự hiện tại, sau đó gọi
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}0 với từng ký tự đó. Tương tự như vậy, ta gọi
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}1 từ các ký tự ở
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}0 và rồi
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}3. Tới
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}3, ta đã duyệt hết các vị trí và không thể thử thêm nữa, nên có thể in ra xâu.
int n;
string curString;
void genString[int pos]
{
if [pos > n]
{
cout P_{i - 1}$, hay mọi phần tử đều lớn hơn hẳn phần tử được dựng trước đó. Giả sử ta đã xây dựng được dãy đến vị trí thứ $i$, và $P_i$ là giá trị cuối cùng được thêm vào. Tại vị trí thứ $i+1$, do có $P_{i + 1} > P_i$, nên ta chỉ thử các số từ $P_{i} + 1$ đến $n$.Phần đệ quy sẽ kết thúc khi tập con đã có đủ $k$ phần tử.
Sử dụng ý tưởng trên ta cài đặt như sau:
int n, k;
vector curSubset;
//Hàm đệ quy
void printSubset[]
{
for [int i : curSubset] cout k;
curSubset.clear[];
genSubset[1];
return 0;
}
Mở rộng: Vẫn đề bài trên nhưng giờ bỏ đi điều kiện "Hai tập con là hoán vị của nhau chỉ tính là một." thì chúng ta sẽ làm như thế nào? [gợi ý: lúc này thay vì có mọi số lớn hơn số liền trước, ta chỉ cần các số trong tập hợp khác nhau là đủ]
Còn về hướng biểu diễn dãy nhị phân, bạn đọc hãy thử tự suy nghĩ và cài đặt. Trong lập trình thi đấu, khi phải duyệt mọi tập con, cách này dễ đọc và hiệu quả hơn hẳn. Nhưng đây là bài giới thiệu về đệ quy nên là…
Bài toán phân tích số
Bài toán: Ở một quốc gia có $n$ loại tiền gồm các mệnh giá $a_1, a_2, …, a_n$ [$n \leq 10$]. Có những cách nào để lấy các tờ tiền sao cho tổng mệnh giá của chúng là $S$? Biết rằng mỗi mệnh giá tiền có thể được lấy nhiều lần và hai cách lấy là hoán vị của nhau chỉ tính là một. Ví dụ: với 3 loại tiền mệnh giá $10, 20, 50$, có $10$ cách lấy tiền để có tổng là $100$, bao gồm $10$ tờ $10$, hoặc $2$ tờ $50$, hoặc $3$ tờ $10$, $1$ tờ $20$ và $1$ tờ $50$, …
Một cách rất tự nhiên, chúng ta sẽ tiếp tục làm tương tự như bài trước: lưu các tờ tiền đã có vào một tập hợp, sau đó lấy tiền sao cho tờ sau có mệnh giá không nhỏ hơn tờ trước. Hàm đệ quy như thế sẽ có dạng
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}
5.
Vậy thì khi nào chúng ta dừng lại? Đó là khi tổng số tiền chúng ta đã lấy được đạt mức yêu cầu, hoặc lớn hơn. Khi đó, kết quả hợp lệ sẽ là trường hợp số tiền đạt mức yêu cầu.
Trong quá trình cài đặt, song song với việc duy trì một tập hợp tiền đang xây dựng
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}
6, chúng ta sẽ cần lưu thêm một giá trị tổng
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}
7 để đơn giản tính toán.
int n, a[15];
long long S, curMoneySum;
vector curMoneySet;
void printMoneySet[]
{
for [auto i : curMoneySet] cout > S;
for [int i = 1; i > a[i];
curMoneySet.clear[];
curMoneySum = 0;
genMoneySet[1];
return 0;
}
Nếu bạn đọc để ý kỹ thì chúng ta không sử dụng tham số
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}
8 trong hàm
void backtrack[int pos]
{
// Trường hợp cơ sở
if []
{
return;
}
//Phần đệ quy
for []
{
backtrack[pos + 1];
}
}
9 vào mục đích gì cả. Có thể bỏ tham số này đi, và chúng ta có một hàm đệ quy không tham số. Tham số này ở đây chỉ giúp chúng ta hiểu hàm này hơn thôi.
Bài toán xếp hậu
Xếp hậu là bài toán rất kinh điển, có lẽ nếu bạn học đệ quy quay lui ở đâu thì cũng sẽ gặp.
Bài toán: Tìm tất cả các cách xếp $n$ [$n \leq 12$] quân Hậu lên một bàn cờ $n \times n$ sao cho không có hai quân Hậu nào có thể ăn được nhau. Nếu có hai cách là hoán vị của nhau [về vị trí] thì chỉ tính là một, ví dụ hai tập hợp ${[1, 2], [3, 4], [5, 6]}$ và ${[1, 2], [5, 6], [3, 4]}$ chỉ lấy $1$. Hai quân Hậu được gọi là có thể ăn được nhau nếu chúng nằm cùng hàng, cột hoặc đường chéo của bàn cờ.
Phân tích: Giả sử quân Hậu thứ $i$ nằm ở hàng $x_i$ và cột $y_i$. Cách gọi này hơi ngược một chút so với hệ toạ độ Decartes thông thường nhưng nó sẽ rất hợp cho những bài toán liên quan đến bảng.
Khi nào thì hai quân Hậu $A$ và $B$ ăn nhau?
- Khi $A$ và $B$ nằm cùng hàng, tức là $x_A = x_B$.
- Khi $A$ và $B$ nằm cùng cột, tức là $y_A = y_B$.
- Khi $A$ và $B$ nằm trên cùng đường chéo. Lúc này có hai trường hợp:
- $x_A + y_A = x_B + y_B$
- $x_A - y_A = x_B - y_B$
Đối với đường chéo, bạn đọc có thể tự kiểm chứng thấy rằng, hiệu hoặc tổng của chỉ số hàng và chỉ số cột luôn luôn là một số không đổi đối với hai phần tử cùng đường chéo, lần lượt ứng với đường chéo chính [hướng tây bắc - đông nam] và đường chéo phụ [hướng đông bắc - tây nam].
Vậy thì, việc của chúng ta bây giờ chỉ là sinh ra những bộ toạ độ đôi một thoả mãn các điều kiện trên thôi. Chúng ta sẽ sinh các bộ toạ độ này lần lượt theo từng hàng, và đảm bảo rằng quân Hậu sau sẽ không cùng cột và cùng đường chéo với quân Hậu trước. Để khỏi phải
int n;
string curString;
void genString[int pos]
{
if [pos > n]
{
cout n]
{
cout n]
{
cout n]
{
cout n]
{
cout n]
{
cout n]
{
cout n]
{
cout n]
{
cout n]
{
cout