Đệ Quy trong Java 🎯
🎯 Mục tiêu: Học cách sử dụng đệ quy để giải quyết các bài toán phức tạp bằng cách chia nhỏ chúng thành các bài toán con trong Java.
Giới thiệu 📝
Đệ quy là một kỹ thuật lập trình trong đó một phương thức gọi lại chính nó để giải quyết một vấn đề. Đệ quy giúp code ngắn gọn và dễ hiểu hơn, đặc biệt khi giải quyết các bài toán có cấu trúc đệ quy tự nhiên.
💡 Fun Fact: Đệ quy được sử dụng rộng rãi trong các thuật toán như quicksort, mergesort, và trong việc duyệt cây thư mục.
1. Cú Pháp Cơ Bản ⚡
Đệ Quy Đơn Giản
public class Recursion {
// Đệ quy tính giai thừa
public static int factorial(int n) {
// Điều kiện dừng
if (n <= 1) {
return 1;
}
// Bước đệ quy
return n * factorial(n - 1);
}
}
Đệ Quy Có Điều Kiện
public class Recursion {
// Đệ quy tính số Fibonacci
public static int fibonacci(int n) {
// Điều kiện dừng
if (n <= 1) {
return n;
}
// Bước đệ quy
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
2. Các Loại Đệ Quy 🔄
Đệ Quy Đuôi
public class TailRecursion {
// Đệ quy đuôi tính giai thừa
public static int factorial(int n, int result) {
// Điều kiện dừng
if (n <= 1) {
return result;
}
// Bước đệ quy đuôi
return factorial(n - 1, n * result);
}
// Phương thức wrapper
public static int factorial(int n) {
return factorial(n, 1);
}
}
Đệ Quy Gián Tiếp
public class IndirectRecursion {
// Phương thức A gọi B
public static void methodA(int n) {
if (n > 0) {
System.out.println("A: " + n);
methodB(n - 1);
}
}
// Phương thức B gọi A
public static void methodB(int n) {
if (n > 0) {
System.out.println("B: " + n);
methodA(n - 1);
}
}
}
3. Ví Dụ Thực Tế 🚀
Quản Lý Thư Mục
public class DirectoryManager {
public static void listFiles(String path, int level) {
File dir = new File(path);
File[] files = dir.listFiles();
if (files != null) {
for (File file : files) {
// In khoảng trắng dựa vào cấp độ
for (int i = 0; i < level; i++) {
System.out.print(" ");
}
System.out.println(file.getName());
// Đệ quy nếu là thư mục
if (file.isDirectory()) {
listFiles(file.getPath(), level + 1);
}
}
}
}
}
Tính Toán Biểu Thức
public class ExpressionCalculator {
public static double evaluate(String expression) {
// Loại bỏ khoảng trắng
expression = expression.replaceAll("\\s+", "");
// Điều kiện dừng: số đơn lẻ
if (expression.matches("\\d+")) {
return Double.parseDouble(expression);
}
// Tìm toán tử cuối cùng
int operatorIndex = findLastOperator(expression);
if (operatorIndex == -1) {
throw new IllegalArgumentException("Invalid expression");
}
// Chia biểu thức thành hai phần
String left = expression.substring(0, operatorIndex);
String right = expression.substring(operatorIndex + 1);
char operator = expression.charAt(operatorIndex);
// Tính toán đệ quy
double leftValue = evaluate(left);
double rightValue = evaluate(right);
return calculate(leftValue, rightValue, operator);
}
private static int findLastOperator(String expression) {
int lastIndex = -1;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (c == '+' || c == '-' || c == '*' || c == '/') {
lastIndex = i;
}
}
return lastIndex;
}
private static double calculate(double a, double b, char operator) {
switch (operator) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
default: throw new IllegalArgumentException("Invalid operator");
}
}
}
Tìm Kiếm Nhị Phân
public class BinarySearch {
public static int search(int[] arr, int target, int left, int right) {
// Điều kiện dừng
if (left > right) {
return -1; // Không tìm thấy
}
// Tìm điểm giữa
int mid = left + (right - left) / 2;
// So sánh và đệ quy
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return search(arr, target, left, mid - 1);
} else {
return search(arr, target, mid + 1, right);
}
}
// Phương thức wrapper
public static int search(int[] arr, int target) {
return search(arr, target, 0, arr.length - 1);
}
}
4. Best Practices ✅
-
Luôn Có Điều Kiện Dừng
// Không nên
public static int infiniteRecursion(int n) {
return infiniteRecursion(n - 1); // Không có điều kiện dừng
}
// Nên
public static int factorial(int n) {
if (n <= 1) { // Điều kiện dừng
return 1;
}
return n * factorial(n - 1);
} -
Sử Dụng Đệ Quy Đuôi Khi Có Thể
// Không nên
public static int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1); // Không phải đệ quy đuôi
}
// Nên
public static int factorial(int n, int result) {
if (n <= 1) {
return result;
}
return factorial(n - 1, n * result); // Đệ quy đuôi
} -
Tránh Đệ Quy Quá Sâu
// Không nên
public static int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2); // Đệ quy quá sâu
}
// Nên
public static int fibonacci(int n) {
if (n <= 1) return n;
int prev = 0, curr = 1;
for (int i = 2; i <= n; i++) {
int next = prev + curr;
prev = curr;
curr = next;
}
return curr;
}
5. Lỗi Thường Gặp ⚠️
-
Stack Overflow
// Lỗi
public static void infiniteRecursion() {
infiniteRecursion(); // Gọi đệ quy vô hạn
}
// Đúng
public static void recursion(int n) {
if (n <= 0) return; // Điều kiện dừng
recursion(n - 1);
} -
Quên Cập Nhật Tham Số
// Lỗi
public static void process(int n) {
if (n > 0) {
System.out.println(n);
process(n); // Quên giảm n
}
}
// Đúng
public static void process(int n) {
if (n > 0) {
System.out.println(n);
process(n - 1); // Giảm n
}
} -
Đệ Quy Không Hiệu Quả
// Lỗi
public static int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2); // Tính toán trùng lặp
}
// Đúng
public static int fibonacci(int n, Map<Integer, Integer> memo) {
if (n <= 1) return n;
if (memo.containsKey(n)) return memo.get(n);
int result = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
memo.put(n, result);
return result;
}
💡 Lời khuyên: Hãy thực hành với các ví dụ thực tế để hiểu rõ hơn về cách sử dụng đệ quy trong các tình huống khác nhau.
Tiếp Theo 🎯
Trong các bài học tiếp theo, chúng ta sẽ:
- Học cách sử dụng tính đa hình (Polymorphism)
- Thực hành với interface và abstract class
- Tìm hiểu về package và import
- Học cách xử lý ngoại lệ (Exception Handling)