Đệ quy trong lập trình
Đệ quy là một khái niệm trong lập trình mà một hàm gọi chính nó để giải quyết các phiên bản nhỏ hơn của cùng một vấn đề. Dưới đây là một số điểm quan trọng về đệ quy:
Mục lục
Ứng dụng của đệ quy:
- Tính toán toán học: Ví dụ, tính giai thừa của một số.
- Duyệt qua cấu trúc dữ liệu phân cấp: Ví dụ, duyệt qua cây (tree).
Ý tưởng chính:
Giải quyết trường hợp cơ bản trước, sau đó gọi hàm cho một phiên bản giảm thiểu vấn đề so với phiên bản ban đầu.
Lợi ích của đệ quy:
- Đơn giản hóa vấn đề phức tạp: Đặc biệt khi có cấu trúc lặp lại.
- Dễ đọc và hiểu: Một số vấn đề tự nhiên được mô tả bằng cách đệ quy dễ hiểu hơn so với cách giải quyết không đệ quy.
Ví dụ sử dụng đệ quy để tính giai thừa:
Giai thừa của một số nguyên dương (n) (ký hiệu là (n!)) được tính bằng cách nhân tất cả các số nguyên từ 1 đến (n).
Ví dụ: (5! = 5 * 4 * 3 * 2 * 1 = 120).
public class GiaiThua {
// Phương thức đệ quy để tính giai thừa
public static int tinhGiaiThua(int n) {
if (n == 0) {
// Điều kiện cơ sở: 0! = 1
return 1;
} else {
// Công thức đệ quy: n! = n * (n - 1)!
return n * tinhGiaiThua(n - 1);
}
}
public static void main(String[] args) {
int n = 5; // Số nguyên cần tính giai thừa
int ketQua = tinhGiaiThua(n); // Gọi phương thức đệ quy
System.out.println("Giai thừa của " + n + " là: " + ketQua);
}
}
Ví dụ về sử dụng đệ quy để in ra một cấu trúc dữ liệu dạng cây:
import java.util.ArrayList;
import java.util.List;
// Class representing each node in the tree (i.e., an employee)
class Employee {
String name;
String position;
List<Employee> subordinates;
// Constructor
public Employee(String name, String position) {
this.name = name;
this.position = position;
this.subordinates = new ArrayList<>();
}
// Method to add a subordinate
public void addSubordinate(Employee employee) {
subordinates.add(employee);
}
}
public class OrganizationStructure {
// Recursive method to traverse and print the hierarchical data
public static void printHierarchy(Employee employee, int level) {
// Print the current employee's name and position
// The 'level' variable helps to add indentation for the hierarchy
for (int i = 0; i < level; i++) {
System.out.print("\t"); // Indentation to show hierarchy level
}
System.out.println(employee.position + ": " + employee.name);
// Recursively print all subordinates
for (Employee subordinate : employee.subordinates) {
printHierarchy(subordinate, level + 1);
}
}
public static void main(String[] args) {
// Creating employees (nodes in the hierarchy)
Employee ceo = new Employee("John", "CEO");
Employee vpMarketing = new Employee("Sara", "VP Marketing");
Employee vpSales = new Employee("Tom", "VP Sales");
Employee marketingManager = new Employee("Alice", "Marketing Manager");
Employee salesManager = new Employee("Bob", "Sales Manager");
Employee salesRep1 = new Employee("Kate", "Sales Representative");
Employee salesRep2 = new Employee("Jim", "Sales Representative");
// Constructing the organizational hierarchy (tree)
ceo.addSubordinate(vpMarketing);
ceo.addSubordinate(vpSales);
vpMarketing.addSubordinate(marketingManager);
vpSales.addSubordinate(salesManager);
salesManager.addSubordinate(salesRep1);
salesManager.addSubordinate(salesRep2);
// Printing the hierarchy starting from the CEO
printHierarchy(ceo, 0);
}
}
Các vấn đề thường gặp khi sử dụng đệ quy:
Đệ quy vô hạn (Infinite Recursion): Nếu không có trường hợp cơ sở (base case) hoặc trường hợp cơ sở được định nghĩa sai, hàm sẽ tiếp tục gọi chính nó mà không ngừng.
Tràn ngăn xếp (Stack Overflow): Đệ quy sâu có thể vượt quá bộ nhớ được cấp phát cho ngăn xếp gọi, gây ra lỗi và crash.
Cách ngăn đệ quy (Recursion Breaking Methods):
Trường hợp cơ sở (Base Case): Đảm bảo rằng các trường hợp cơ sở được định nghĩa đúng để dừng đệ quy.
Phương pháp lặp (Iterative Approach): Đôi khi đệ quy có thể được thay thế bằng lặp (giải pháp dựa trên vòng lặp) để tránh đệ quy sâu.
Ví dụ: Vòng lặp vô hạn nếu không xử lý trường hợp cơ sở.
Bài tập
1. Tính giai thừa của một số nguyên (Factorial)
Viết hàm đệ quy tính giai thừa của một số nguyên n. Công thức giai thừa:
n! = n * (n-1)!(với n > 0)0! = 1
2. Tính dãy Fibonacci
Viết hàm đệ quy tính số Fibonacci thứ n. Dãy Fibonacci được định nghĩa như sau:
F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2)(với n >= 2)
3. Đảo ngược chuỗi (Reverse a string)
Viết hàm đệ quy để đảo ngược một chuỗi ký tự. Ý tưởng là lấy ký tự đầu tiên và đặt nó vào cuối chuỗi đã được đảo ngược.
4. Tính tổng dãy số từ 1 đến n
Viết hàm đệ quy để tính tổng các số từ 1 đến n. Công thức:
sum(n) = n + sum(n-1)(với n > 0)sum(0) = 0
5. Đếm số chữ số của một số nguyên
Viết hàm đệ quy để đếm số chữ số của một số nguyên dương n. Gợi ý: Số chữ số của n được tính bằng cách chia n cho 10 cho đến khi n == 0.
6. Tìm ước chung lớn nhất (GCD)
Viết hàm đệ quy để tìm ước chung lớn nhất của hai số nguyên a và b sử dụng thuật toán Euclid. Công thức:
gcd(a, b) = gcd(b, a % b)(với a % b ≠ 0)gcd(a, 0) = a
7. Tìm số nhị phân của một số nguyên
Viết hàm đệ quy để chuyển đổi một số nguyên dương thành dạng nhị phân.
8. Tìm số lũy thừa (Exponentiation)
Viết hàm đệ quy tính lũy thừa của một số nguyên x mũ n. Công thức:
power(x, n) = x * power(x, n-1)(với n > 0)power(x, 0) = 1
9. Kiểm tra chuỗi Palindrome
Viết hàm đệ quy để kiểm tra xem một chuỗi có phải là chuỗi palindrome (đối xứng) hay không. So sánh ký tự đầu và cuối, rồi gọi đệ quy với chuỗi con ở giữa.
10. Tìm số hoán vị của một dãy số
Viết hàm đệ quy để in ra tất cả các hoán vị của một dãy số hoặc chuỗi. Bài toán này sử dụng kỹ thuật đệ quy để hoán đổi các phần tử và tìm ra các hoán vị khác nhau.
11. Đảo ngược một Stack bằng Đệ quy
Đề bài:
Viết một chương trình Java để đảo ngược các phần tử trong một Stack bằng cách sử dụng đệ quy. Bạn không được phép sử dụng cấu trúc lặp (như vòng for hoặc while). Bạn chỉ được phép sử dụng các thao tác đẩy (push) và lấy phần tử ra (pop) của Stack.
Gợi ý:
- Viết hàm đệ quy để đảo ngược toàn bộ Stack.
- Viết hàm phụ trợ để chèn một phần tử vào đáy của Stack
Bài tập 071024:
Dưới đây là một số bài tập bổ sung để bạn ôn tập và kết hợp các kiến thức về stack, queue, HashTable, HashMap và đệ quy:
1. Kiểm tra ngoặc đúng trong biểu thức toán học
Viết chương trình sử dụng stack để kiểm tra xem các dấu ngoặc ( (), {}, [] ) có đóng mở đúng thứ tự trong một biểu thức toán học hay không.
- Input: Một chuỗi biểu thức chứa các dấu ngoặc.
- Output: `true` nếu các dấu ngoặc đúng, `false` nếu sai.
2. **Chuyển đổi từ Infix sang Postfix
Viết chương trình chuyển đổi một biểu thức Infix (biểu thức trung tố) sang Postfix (hậu tố) sử dụng stack.
- Input: Chuỗi biểu thức toán học Infix (ví dụ: "A + B * (C - D)").
- Output: Chuỗi biểu thức Postfix.
3. Triển khai Queue bằng hai Stack
Viết chương trình triển khai một queue bằng cách sử dụng hai stack. Bạn cần triển khai hai phương thức chính: `enqueue` (thêm phần tử vào hàng đợi) và `dequeue` (lấy phần tử khỏi hàng đợi).
4. Kiểm tra tính đối xứng của số bằng Queue
Viết chương trình kiểm tra xem một số nguyên có phải là số đối xứng (palindrome number) hay không bằng cách sử dụng queue.
- Input: Một số nguyên.
- Output: `true` nếu là số đối xứng, `false` nếu không.
5. Tìm phần tử xuất hiện nhiều nhất trong mảng
Viết chương trình sử dụng HashMap để tìm phần tử xuất hiện nhiều nhất trong một mảng số nguyên.
- Input: Một mảng số nguyên.
- Output: Phần tử xuất hiện nhiều nhất và số lần xuất hiện của nó.
6. Đếm số lần xuất hiện của ký tự trong chuỗi
Viết chương trình sử dụng HashMap để đếm số lần xuất hiện của mỗi ký tự trong một chuỗi.
- Input: Một chuỗi ký tự.
- Output: Một HashMap trong đó key là ký tự, value là số lần xuất hiện của ký tự đó.
7. Phân tích dãy số Fibonacci bằng HashMap và Đệ quy
Viết chương trình để tính giá trị của số Fibonacci thứ `n` bằng cách sử dụng **đệ quy** và HashMap để lưu trữ các giá trị đã tính trước đó (memoization).
- Input: Một số nguyên `n`.
- Output: Số Fibonacci thứ `n`.
8. Hệ thống Cache LRU (Least Recently Used)
Triển khai hệ thống cache sử dụng thuật toán Least Recently Used (LRU). Sử dụng HashMap và danh sách liên kết kép (LinkedList) để quản lý việc lưu trữ và truy cập dữ liệu.
- Input: Số lượng cache và các yêu cầu truy cập.
- Output: Trạng thái của cache sau mỗi lần truy cập.
9. Đệ quy và HashMap để tìm số ước chung lớn nhất
Sử dụng đệ quy để tìm ước chung lớn nhất (GCD) của hai số, đồng thời lưu trữ các kết quả trung gian bằng cách sử dụng HashMap để tránh tính toán lại.
- Input: Hai số nguyên.
- Output: GCD của hai số.
10. Đảo ngược Queue bằng Đệ quy
Viết chương trình sử dụng đệ quy để đảo ngược các phần tử trong một queue mà không sử dụng bất kỳ cấu trúc lặp nào.
