C không những cho phép hàm này gọi tới hàm khác, mà nó còn cho phép từ một điểm trong thân của một hàm gọi chính hàm đó. Hàm như vậy gọi là đệ quy. Vậy một chương trình sẽ chạy thế nào nếu như áp dụng đệ quy ? Cùng tham khảo ở phần dưới đây nhé
Cách dùng đệ quy
Phương pháp đệ quy thường áp dụng cho các bài toán phụ thuộc tham số có 2 đặc điểm sau :
Bài toán dễ dàng giải quyết trong một số trường hợp riêng ứng với các giá trị đặc biệt của tham số. Ta gọi đây là trường hợp suy biến.
Trong trường hợp tổng quát, bài toán có thể quy về một bài toán cùng dạng nhưng giá trị tham số thì bị thay đổi. Và saiu một số hữu hạn các bước biến đổi đệ quy, sẽ dẫn đến trường hợp suy biến.
Các ví dụ về đệ quy
Mục này sẽ trình bày một số ví dụ đơn giản nhằm minh họa một cách dễ hiểu hàm đệ quy Ví dụ 1 : Xét bài toán tìm USCLN của 2 số nguyên dương a,b+ Trường hợp suy biến là trường hợp a=b USCLN(a,b)=a. + Trường hợp x khác y thì có thể đệ quy như sau :USCLN(a,b)=USCLN(a-b,b) nếu a>b USCLN(a,b)=USCLN(a,b-a) nếu a
Hàm tìm USCLN áp dụng đệ quy được viết như sau :
Đệ quy trong C++ là 1 phương thức vô cùng quan trọng và là cơ sở của rất rất đa dạng thuật toán. Vì vậy, hiểu được đệ quy sẽ giúp bạn dễ dàng tiếp cận và học hỏi thêm nhiều kiến thức khác về lập trình. Trong bài viết ngày này, Techacademy sẽ chia sẻ với các bạn tất tần tật mọi thứ về đệ quy cùng với các bài tập đệ quy có lời giải chi tiết để giúp bạn hiểu rõ hơn về nó nữa đấy!
I. Đệ Quy Trong C++ Là Gì
Đệ quy trong C++ là quá trình trong đó một phương thức gọi lại chính nó một cách liên tiếp. Một hàm trong C++ gọi lại chính nó được gọi là phương thức đệ quy. Trong một hàm đệ quy sẽ gồm có điều kiện dừng và lời gọi hàm đệ quy, cú pháp cụ thể như sau:
Kiểu_trả_về Tên_hàm (Các_tham_số)
{
Điều_kiện_dừng;
return Tên_hàm (Các_tham_số_mới) ;
// hoặc một biểu thức có chứa lời gọi hàm.
}
Để giúp bạn dễ hình dung hơn thì dưới đây sẽ là ví dụ về hàm đệ quy giúp tính giai thừa của một số tự nhiên:
long long Giaithua(int n)
{
if (n==0 || n==1)
return 1;
else
return Giaithua(n-1) * n;
}
Giải thích thuật toán: Ở đây, điều kiện dừng chính là n=0 hoặc là n=1 thì sẽ trả về giá trị là 1 ( Do 0!=1!=1). Ngược lại, nếu n>1, hàm sẽ trả về n*Giaithua(n-1). Chẳng hạn ta cho n nhận giá trị là 3, chương trình sẽ thực thi như sau:
Vậy mục đích của hàm đệ quy là chia vấn đề thành những vấn đề nhỏ hơn cho đến lúc đạt được điều kiện cơ bản. Lưu ý quan trọng khi dùng đệ quy là bắt buộc phải có điều kiện dừng, nếu không có thì sẽ làm hàm gọi hàm liên tục không có điểm dừng và dẫn đến chương trình không thể kết thúc được.
Đệ Quy Trong C++ Là Gì
II. Cách Sử Dụng Đệ Quy Trong C++
Trong C++, một hàm gọi chính nó ta gọi đó là hàm đệ quy, nghĩa là trong thân hàm sẽ gọi đến chính tên hàm hiện tại và truyền đúng những tham số mà hàm đã khai báo.
Cú pháp: Cú pháp của hàm đệ quy trong C++ như sau:
HamDeQuy(){
HamDeQuy(); //goi lai chinh no
}
Ví dụ: Chúng ta cùng xem một ví dụ đơn giản về hàm đệ quy trong C++ đó là tính giai thừa của một số nguyên.
Trước khi giải bài toán tính giai thừa của một số nguyên trong C++ chúng ta cùng nhớ lại công thức tính giai thừa trong toán học trước đã nhé.
Theo định nghĩa giai thừa ta có:
0! = 1
n! = 1 * 2 * 3 * … * n
Vậy là ta đã có công thức tính giai thừa của một số nguyên rồi. Nếu n = 0 thì giai thừa bằng 1. Nếu n > 0 thì giai thừa sẽ là tích từ 1 đến n. Và không có giai thừa của số âm.
Giải bằng vòng lặp For
Trước khi đi vào giải bài toán trên bằng hàm đệ quy, mình sẽ giải bằng vòng lặp for trong C++ trước nhé.
Ví dụ
#include
using namespace std;
int main()
{
int n;
while(true) {
int giaithua = 1;
cout << "Nhap so n: ";
cin >> n;
//Nhap n nho hon 0 de thoat khoi vong lap
if(n < 0) {
cout << " So am khong co giai thua" << endl;
break;
}
if ( n > 0) {
for(int i = 1; i <=n; i++) {
giaithua = giaithua * i;
}
}
cout << " Giai thua cua " << n << " la: " << giaithua << endl;
}
return 0;
}
Và kết quả sau khi thực thi chương trình trên như sau:
Cách Sử Dụng Đệ Quy Trong C++
Như vậy, để giải quyết bài toán giai thừa của một số bằng vòng lặp for trong C++ rất đơn giản phải không các bạn? Bây giờ mình sẽ giải bài toán giai thừa trên bằng hàm đệ quy trong C++.
Giải bằng đệ quy C++
Các bạn để ý kỹ thì thấy thuật toán tính giai thừa sẽ như sau: Giả sử cần tính 5!, lúc này quy luật của nó sẽ là.
5! = 4! * 5
4! = 3! * 4
3! = 2! * 3
2! = 1! * 2
1! = 1
Thay các vế vào ta sẽ được quy luật: 5! = 1 * 2 * 3 * 4 * 5.
Giả sử ta có hàm tính gian thừa của một số tên là GT, lúc này thay vào công thức trên ta được như sau:
GT(5) = GT(4) * 5
GT(4) = GT(3) * 4
GT(3) = GT(2) * 3
GT(2) = GT(1) * 2
GT(1) = 1
Vậy, ta có thể áp dụng giải thuật đệ quy C++ để giải quyết, bằng cách bên trong thân hàm sẽ gọi đến chính hàm đó.
Ví dụ
#include
using namespace std;
int GiaiThua(int n) {
// Trường hợp người dùng nhập
if (n == 1)
return 1;
else
return (n * GiaiThua(n - 1));
}
int main()
{
int n;
while(true) {
cout << "Nhap so n: ";
cin >> n;
//Nhap n nho hon 0 de thoat khoi vong lap
if(n < 0) {
cout << " So am khong co giai thua" << endl;
break;
}
cout << " Giai thua cua " << n << " la: " << GiaiThua(n) << endl;
}
return 0;
}
Và kết quả sau khi thực thi chương trình trên như sau:
Cách Sử Dụng Đệ Quy Trong C++
Đối với các bạn mới bắt đầu học lập trình thì cách giải bài toán giai thừa trên bằng vòng lặp for sẽ dễ hiểu hơn rất nhiều so với việc giải bằng hàm đệ quy. Tuy nhiên, các bạn đừng quá lo lắng, mình sẽ giải thích đoạn code cho các bạn bạn dễ hiểu.
Giả sử mình nhập n = 5 thì chương trình trên sẽ chạy như sau:
Mục đích của hàm đệ quy là chia vấn đề thành các vấn đề nhỏ hơn cho đến khi đạt được điều kiện cơ bản.
Ví dụ trong chương trình giai thừa ở trên, chúng ta đang giải quyết hàm giai thừa GiaiThua(n) bằng cách gọi hàm giai thừa nhỏ hơn GiaiThua(n-1), điều này được lặp lại liên tục cho đến khi giá trị n đạt đến điều kiện cơ sở (GiaiThua(1) = 1).
III. Đệ Quy Quay Lui Trong C++
Quay lui là 1 kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.
Tư tưởng
Dùng để giải bài toán liệt kê những cấu hình. Mỗi cấu hình được xây dựng bằng từng phần tử. Mỗi phần tử lại được chọn bằng cách thử toàn bộ các khả năng.
Các bước trong việc liệt kê cấu hình dạng X[1…n]:
Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận những giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
Xét đa số giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]…tiếp tục như vậy cho đến bước:
…
…
Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
Thông báo cấu hình tìm được.
Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search).
Mô hình thuật toán
Mã giả cho thuật toán quay lui.
Backtracking(k) {
for([Mỗi phương án chọn i(thuộc tập D)]) {
if ([Chấp nhận i]) {
[Chọn i cho X[k]];
if ([Thành công]) {
[Đưa ra kết quả];
} else {
Backtracking(k+1);
[Bỏ chọn i cho X[k]];
}
}
}
}
Ví dụ: Trò chơi Sudoku
Sudoku là một trò chơi khá phổ biến và chắc ai cũng biết. Trò chơi như sau: có một hình vuông được chia thành 9×9 ô vuông con. Mỗi ô vuông con có giá trị trong khoảng từ 1 đến 9. Ban đầu hình vuông có một số ô vuông con cho trước (có điền sẵn số) và còn lại là trống. Hãy điền các số từ 1-9 vào các ô con lại sao cho: hàng ngang là các số khác nhau từ 1 đến 9, hàng dọc là các số khác nhau từ 1 đến 9, và mỗi khối 3×3 chính là các số khác nhau từ 1 đến 9. Sau đây là 1 ví dụ về đề bài và lời giải:
Đệ Quy Quay Lui Trong C++
Áp dụng quay lui để giải bài toán sudoku. Ý tưởng: Mỗi bước tìm tập các giá trị khả dĩ để điền vào ô trống, và sau đó đệ quy để điền ô tiếp theo. Giả mã của thuật toán (ở đây chú ý mảng chỉ có kích thước 9×9×9)
void solveSudoku(int S[][9], int x, int y){
if(y == 9){
if(x == 8){
printSolution(S);
exit(0);
} else {
solveSudoku(S, x+1,0);
}
} else if(S[x][y] == 0){
for (int k = 1; k <=9; k++){
if(checkValid(S,x,y,k)){
S[x][y] = k;
solveSudoku(S, x, y+1);
S[x][y] = 0;
}
}
} else {
solveSudoku(S,x,y+1);
}
}
boolean checkValid(int S[][9], int x, int y, int k){
for(int i = 0; i <9 ; i++){
if(S[x][i] == k) return false;
}
for(int i = 0; i <9 ; i++){
if(S[i][y] == k) return false;
}
int a = x/3, b = y/3;
for(int i = 3*a; i < 3*a+3; i++){
for(int j = 3*b; j < 3*b+3; j++){
if(S[i][j] == k) return false;
}
}
return true;
}
Nhận xét
Ưu điểm: Việc quay lui là thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian chạy.
Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải các nhược điểm sau:
Rơi vào tình trạng “thrashing”: qúa trình tìm kiếm cứ gặp phải bế tắc với cùng một nguyên nhân.
Thực hiện các công việc dư thừa: Mỗi lần chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
Không sớm phát hiện được các khả năng bị bế tắc trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết đc nhánh tìm kiếm sẽ đi vào bế tắc.
IV. Bài Tập Đệ Quy Quay Lui Trong C++
+ Tìm Ước Chung Lớn Nhất Và Bội Chung Nhỏ Nhất Bằng Đệ Quy
Hàm đệ quy là những hàm gọi lại chính nó. Nó hữu dụng trong các tác vụ như sắp xếp hoặc tính toán các số giai thừa… Hàm đệ quy tương ứng với khái niệm quy nạp trong toán học.
Bài tập 1. Thuật toán Euclide tìm ước chung lớn nhất
Viết chương trình tìm ước chung lớn nhất của 2 số nguyên dương a, b bằng thuật toán. Euclide được định nghĩa đệ quy như sau:
[Cài đặt:]
#include
#include
int UCLN(int a, int b) {
if(a==b)
return a;
else if(a>b)
return UCLN(a-b,b);
else
return UCLN(a,b-a);
}
void main() {
clrscr();
int a,b;
cout<<"Nhap a = ";
cin>>a;
cout<<"Nhap b = ";
cin>>b;
cout<<"Uoc chung lon nhat cua "<Bài tập 2. Tìm ước chung lớn nhất của n số nguyên