I. LÝ THUYẾT
Thuật toán đệ quy là một phương pháp trong lập trình khi một hàm tự gọi chính nó để giải quyết một bài toán. Đệ quy thường được sử dụng để giải quyết các bài toán có tính chất lặp đi lặp lại hoặc bài toán có thể được chia nhỏ thành các bài toán con giống nhau. Một thuật toán đệ quy thường có hai phần chính:
– Trường hợp cơ bản (base case): Đây là điều kiện dừng của thuật toán đệ quy. Khi thuật toán gọi chính nó, nó kiểm tra trường hợp cơ bản để quyết định liệu nó nên dừng lại và trả về kết quả hay tiếp tục gọi chính nó.
– Bước đệ quy (recursive step): Trong phần này, thuật toán gọi chính nó với các đối số khác nhau để giải quyết vấn đề con. Thuật toán sẽ tiếp tục gọi chính nó cho đến khi đạt đến trường hợp cơ bản.
Cấu trúc của hàm đệ quy
Một hàm đệ quy cần có:
- Điều kiện dừng: Là điều kiện để dừng việc gọi đệ quy, tránh rơi vào vòng lặp vô hạn.
- Gọi lại chính nó: Hàm gọi lại chính nó với một trường hợp đơn giản hơn.
II. BÀI TẬP
Bài 1. Tính giai thừa của một số (n!)
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
int main() {
int number = 5;
cout << "Factorial of " << number << " is " << factorial(number) << endl;
return 0;
}
Thuật toán lặp
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
Bài 2. Tính số Fibonacci thứ n
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int number;
cout << "Nhập vị trí của số Fibonacci: ";
cin >> number;
cout << "Số Fibonacci thứ " << number << " là: " << fibonacci(number) << endl;
return 0;
}
Thuật toán lặp:
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int a = 0, b = 1, c;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
Bài 3. Tính tổng các số từ 1 đến n
#include <iostream>
using namespace std;
int sum(int n) {
if (n == 0) return 0;
return n + sum(n - 1);
}
int main() {
int number;
cout << "Nhập một số nguyên dương: ";
cin >> number;
cout << "Tổng các số từ 1 đến " << number << " là: " << sum(number) << endl;
return 0;
}
Bài 4. Tìm ước chung lớn nhất (GCD)
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
int main() {
int a, b;
cout << "Nhập hai số nguyên: ";
cin >> a >> b;
cout << "Ước chung lớn nhất của " << a << " và " << b << " là: " << gcd(a, b) << endl;
return 0;
}
Bài 5. Tìm lũy thừa xn
#include <iostream>
using namespace std;
int power(int x, int n) {
if (n == 0) return 1;
return x * power(x, n - 1);
}
int main() {
int x, n;
cout << "Nhập cơ số (x): ";
cin >> x;
cout << "Nhập số mũ (n): ";
cin >> n;
cout << x << " ^ " << n << " = " << power(x, n) << endl;
return 0;
}
Bài 6. Đếm số chữ số của một số
#include <iostream>
using namespace std;
int countDigits(int n) {
if (n == 0) return 0;
return 1 + countDigits(n / 10);
}
int main() {
int number;
cout << "Nhập một số nguyên: ";
cin >> number;
cout << "Số chữ số của " << number << " là: " << countDigits(number) << endl;
return 0;
}
Bài 7. Đảo ngược chuỗi
#include <iostream>
#include <string>
using namespace std;
void reverseString(string &s, int left, int right) {
if (left >= right) return;
swap(s[left], s[right]);
reverseString(s, left + 1, right - 1);
}
int main() {
string str;
cout << "Nhập một chuỗi: ";
cin >> str;
reverseString(str, 0, str.length() - 1);
cout << "Chuỗi đảo ngược là: " << str << endl;
return 0;
}
Bài 8. Kiểm tra chuỗi đối xứng (Palindrome)
#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(string &s, int left, int right) {
if (left >= right) return true;
if (s[left] != s[right]) return false;
return isPalindrome(s, left + 1, right - 1);
}
int main() {
string str;
cout << "Nhập một chuỗi: ";
cin >> str;
if (isPalindrome(str, 0, str.length() - 1)) {
cout << str << " là chuỗi đối xứng." << endl;
} else {
cout << str << " không là chuỗi đối xứng." << endl;
}
return 0;
}
Bài 9. Tìm dãy con của một chuỗi (Subsequences)
#include <iostream>
#include <string>
using namespace std;
void printSubsequences(string s, string current, int index) {
if (index == s.length()) {
cout << current << endl;
return;
}
// Không chọn ký tự hiện tại
printSubsequences(s, current, index + 1);
// Chọn ký tự hiện tại
printSubsequences(s, current + s[index], index + 1);
}
int main() {
string str;
cout << "Nhập một chuỗi: ";
cin >> str;
cout << "Các dãy con của chuỗi là:" << endl;
printSubsequences(str, "", 0);
return 0;
}
Bài 10. Chuyển đổi số nguyên sang dạng nhị phân
#include <iostream>
using namespace std;
void decToBin(int n) {
if (n > 1) decToBin(n / 2);
cout << n % 2;
}
int main() {
int number;
cout << "Nhập một số nguyên: ";
cin >> number;
cout << "Dạng nhị phân của " << number << " là: ";
decToBin(number);
cout << endl;
return 0;
}
Bài 11. Đảo ngược một số nguyên
#include <iostream>
using namespace std;
void reverseNumber(int n) {
if (n < 10) {
cout << n;
return;
}
cout << n % 10;
reverseNumber(n / 10);
}
int main() {
int number;
cout << "Nhập một số nguyên: ";
cin >> number;
cout << "Số đảo ngược là: ";
reverseNumber(number);
cout << endl;
return 0;
}
Bài 12. Tính tổng các phần tử trong mảng
#include <iostream>
using namespace std;
int sumArray(int arr[], int n) {
if (n <= 0) return 0;
return arr[n - 1] + sumArray(arr, n - 1);
}
int main() {
int n;
cout << "Nhập số lượng phần tử trong mảng: ";
cin >> n;
int arr[n];
cout << "Nhập các phần tử của mảng: ";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << "Tổng các phần tử trong mảng là: " << sumArray(arr, n) << endl;
return 0;
}
Bài 13. Đếm số phần tử trong mảng
#include <iostream>
using namespace std;
int countElements(int arr[], int n) {
if (n <= 0) return 0;
return 1 + countElements(arr, n - 1);
}
int main() {
int n;
cout << "Nhập số lượng phần tử trong mảng: ";
cin >> n;
int arr[n];
cout << "Nhập các phần tử của mảng: ";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << "Số phần tử trong mảng là: " << countElements(arr, n) << endl;
return 0;
}
Bài 14. Tìm giá trị lớn nhất trong mảng
#include <iostream>
using namespace std;
int findMax(int arr[], int n) {
if (n == 1) return arr[0];
return max(arr[n - 1], findMax(arr, n - 1));
}
int main() {
int n;
cout << "Nhập số lượng phần tử trong mảng: ";
cin >> n;
int arr[n];
cout << "Nhập các phần tử của mảng: ";
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cout << "Giá trị lớn nhất trong mảng là: " << findMax(arr, n) << endl;
return 0;
}
Bài 15. Tính tổng các chữ số của một số nguyên
#include <iostream>
using namespace std;
int sumDigits(int n) {
if (n == 0) return 0;
return n % 10 + sumDigits(n / 10);
}
int main() {
int number;
cout << "Nhập một số nguyên: ";
cin >> number;
cout << "Tổng các chữ số của " << number << " là: " << sumDigits(number) << endl;
return 0;
}
Bài 16. Kiểm tra chuỗi đối xứng (Palindrome)
#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(string str, int start, int end) {
if (start >= end) return true;
if (str[start] != str[end]) return false;
return isPalindrome(str, start + 1, end - 1);
}
int main() {
string str;
cout << "Nhập một chuỗi: ";
cin >> str;
if (isPalindrome(str, 0, str.length() - 1)) {
cout << str << " là chuỗi đối xứng." << endl;
} else {
cout << str << " không là chuỗi đối xứng." << endl;
}
return 0;
}
KHI NÀO SỬ DỤNG ĐỆ QUY HOẶC LẶP?
- Sử dụng đệ quy:
- Khi bài toán có tính chất phân rã tự nhiên, như duyệt cây nhị phân, bài toán tháp Hà Nội.
- Khi cần viết code ngắn gọn, dễ đọc hơn.
- Sử dụng lặp:
- Khi ưu tiên hiệu suất và bộ nhớ (ví dụ: bài toán lớn với hàng triệu lần lặp).
- Khi không cần lưu trạng thái trung gian hoặc không cần cấu trúc dữ liệu phức tạp như stack.
TỐI ƯU HÓA THUẬT TOÁN ĐỆ QUY
1. Dùng kỹ thuật Memoization (Nhớ)
Memoization là cách lưu trữ kết quả của các phép tính đã thực hiện để tránh tính lại.
#include <iostream>
#include <vector>
using namespace std;
vector<int> memo;
int fibonacci(int n) {
if (n == 0) return 0; // Điều kiện dừng
if (n == 1) return 1; // Điều kiện dừng
if (memo[n] != -1) return memo[n]; // Nếu đã tính trước, trả về kết quả lưu trữ
memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // Tính toán và lưu kết quả
return memo[n];
}
int main() {
int n;
cout << "Nhập số n: ";
cin >> n;
memo.assign(n + 1, -1); // Khởi tạo mảng memo với giá trị -1
cout << "Số Fibonacci thứ " << n << " là: " << fibonacci(n) << endl;
return 0;
}
2. Dùng thuật toán đệ quy đuôi (Tail Recursion)
Đệ quy đuôi tối ưu không gian bằng cách chuyển trạng thái hiện tại qua tham số hàm.
#include <iostream>
using namespace std;
int fibonacciTail(int n, int a = 0, int b = 1) {
if (n == 0) return a; // Điều kiện dừng
if (n == 1) return b; // Điều kiện dừng
return fibonacciTail(n - 1, b, a + b); // Truyền trạng thái qua tham số
}
int main() {
int n;
cin >> n;
cout << "Số Fibonacci thứ " << n << " là: " << fibonacciTail(n) << endl;
return 0;
}
