Đệ quy trong c+ + là một phương pháp quan trọng và đa dạng, được sử dụng trong nhiều thuật toán. Hiểu về đệ quy sẽ giúp bạn tiếp cận và học thêm nhiều kiến thức khác về lập trình . Trong bài viết này, chúng ta sẽ khám phá đệ quy từ cơ bản đến nâng cao cùng với các bài tập đệ quy có lời giải chi tiết.
I. Đệ Quy Trong C++ Là Gì
Đệ quy trong C++ là quá trình 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, chúng ta 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. }Ví dụ về hàm đệ quy 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: Trong hàm tính giai thừa, chúng ta có điều kiện dừng là n=0 hoặc n=1 thì sẽ trả về giá trị là 1 (vì 0!=1!=1). Ngược lại, nếu n>1, hàm sẽ tính và trả về n*Giaithua(n-1).
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 dừng. Lưu ý quan trọng khi sử dụng đệ quy là bắt buộc phải có điều kiện dừng, nếu không, chương trình sẽ gọi hàm liên tục và không thể kết thúc được.
II. Cách Sử Dụng Đệ Quy Trong C++
Trong C++, chúng ta có thể tạo ra một hàm đệ quy bằng cách gọi chính nó. Cú pháp của hàm đệ quy trong C++ như sau:
HamDeQuy() { HamDeQuy(); // gọi lại chính nó }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 này bằng hàm đệ quy, chúng ta cùng nhớ lại công thức tính giai thừa trong toán học nhé.
Theo định nghĩa, giai thừa có các quy ước như sau:
- 0! = 1
- n! = 1 2 3 … n
Vậy, công thức tính giai thừa cho một số nguyên n là: n! = 1 2 3 … n
#include using namespace std; int GiaiThua(int n) { if (n==0 || n==1) return 1; else return GiaiThua(n-1) * n; } int main() { int n; while(true) { cout "Nhập số n: "; cin >> n; if(n 0) { cout "Số âm không có giai thừa" endl; break; } cout "Giai thừa của " n " là: " GiaiThua(n) endl; } return 0; } Trong ví dụ trên, hàm đệ quy GiaiThua(n) sử dụng phép gọi đệ quy GiaiThua(n-1) để tính giai thừa của số n. Điều kiện dừng trong hàm này là n=0 hoặc n=1, trong trường hợp này hàm trả về giá trị là 1.
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.
III. Đệ Quy Quay Lui Trong C++
Quay lui là một 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 để tiếp tục tìm kiếm.
Tư tưởng:
- Dùng để giải bài toán liệt kê 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).
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 9x9 ô 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 3x3 chính là các số khác nhau từ 1 đến 9.
Hãy á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.
#include using namespace std; const int N = 9; void printSolution(int S[][N]); bool isSafe(int S[][N], int row, int col, int num) { for (int i = 0; i N; i++) if (S[row][i] == num) return false; for (int i = 0; i N; i++) if (S[i][col] == num) return false; int startRow = row - row % 3; int startCol = col - col % 3; for (int i = 0; i 3; i++) for (int j = 0; j 3; j++) if (S[i + startRow][j + startCol] == num) return false; return true; } bool solveSudoku(int S[][N]) { int row, col; bool isEmpty = true; for (row = 0; row N; row++) { for (col = 0; col N; col++) { if (S[row][col] == 0) { isEmpty = false; break; } } if (!isEmpty) break; } if (isEmpty) return true; for (int num = 1; num = N; num++) { if (isSafe(S, row, col, num)) { S[row][col] = num; if (solveSudoku(S)) return true; S[row][col] = 0; } } return false; } void printSolution(int S[][N]) { for (int row = 0; row N; row++) { for (int col = 0; col N; col++) cout S[row][col] " "; cout endl; } } int main() { int S[N][N]; cout "Nhập ma trận Sudoku (0 là ô trống): " endl; for (int row = 0; row N; row++) for (int col = 0; col N; col++) cin >> S[row][col]; if (solveSudoku(S)) { cout "Lời giải của Sudoku là: " endl; printSolution(S); } else { cout "Không có lời giải cho Sudoku!" endl; } return 0; } Trong ví dụ này, chúng ta sử dụng hàm solveSudoku để giải bài toán Sudoku bằng quay lui. Hàm này sử dụng hàm isSafe để kiểm tra xem một số có thể điền vào ô trống hay không.
Các bước để giải bài toán Sudoku:
- Tìm ô trống đầu tiên trong Sudoku.
- Kiểm tra các số từ 1 đến 9 có thể điền vào ô trống đó hay không. Nếu có, thực hiện đệ quy để điền số vào ô và tiếp tục tìm ô trống tiếp theo. Nếu không, quay lại bước trước và thử số khác.
- Khi tất cả các ô trống đều được điền, in ra lời giải Sudoku.
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ãy tìm ước chung lớn nhất (GCD - Greatest Common Divisor) và bội chung nhỏ nhất (LCM - Least Common Multiple) của hai số nguyên dương a và b bằng đệ quy.
#include using namespace std; 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); } int UC(int a[], int n) { if(n==1) return a[0]; else return UCLN(a[n-1],UC(a,n-1)); } int main() { int a, b; cout "Nhập a: "; cin >> a; cout "Nhập b: "; cin >> b; cout "Ước chung lớn nhất của " a " và " b " là: " UCLN(a, b) endl; int n; cout "Nhập số phần tử trong mảng: "; cin >> n; int* arr = new int[n]; cout "Nhập các phần tử trong mảng: "; for(int i=0; i> arr[i]; } cout "Ước chung lớn nhất của các phần tử trong mảng là: " UC(arr, n) endl; delete[] arr; return 0; } Đệ Quy Fibonacci Trong C++
Dãy Fibonacci là dãy số trong đó số tiếp theo là tổng của hai số trước đó. Ví dụ: 1, 1, 2, 3, 5, 8, 13, .... Chúng ta có thể tính số Fibonacci bằng đệ quy và không đệ quy.
#include using namespace std; int Fibonacci(int n) { if (n == 1 || n == 2) return 1; return Fibonacci(n - 1) + Fibonacci(n - 2); } int main() { int n; cout "Nhập n: "; cin >> n; cout "Số Fibonacci thứ " n " là: " Fibonacci(n) endl; return 0; } In Đảo Ngược Một Số Nguyên Dương N
Hãy tạo một hàm để tìm số đảo ngược của một số nguyên dương n. Số đảo ngược là số mà các chữ số của n được đảo ngược thứ tự.
#include using namespace std; void reverseNumber(int n) { if(n 10) { cout n; return; } cout n % 10; reverseNumber(n / 10); } int main() { int n; cout "Nhập n: "; cin >> n; cout "Số đảo ngược của " n " là: "; reverseNumber(n); cout endl; return 0; } Như vậy, đó là một số bài tập đệ quy và quay lui trong ngôn ngữ lập trình c ++. Đệ quy và quay lui là hai khái niệm quan trọng trong lập trình , giúp chúng ta giải quyết các bài toán phức tạp một cách hiệu quả.