Giới thiệu
Giải thuật đệ quy (Recursion) là một trong những phương pháp thường được sử dụng trong lập trình và toán học. Có những bài toán chỉ có thể giải quyết bằng cách sử dụng đệ quy, chẳng hạn như duyệt cây.
Một bài toán được coi là đệ quy khi nó có thể được chia thành các bài toán nhỏ hơn, nhưng có cùng tính chất với bài toán ban đầu. Các bài toán nhỏ lại có thể được chia nhỏ tiếp, cho đến khi không thể chia nhỏ được hoặc đạt được kết quả mong muốn.
Đệ quy trong Java
Trong Java, đệ quy là quá trình mà một phương thức gọi lại chính nó một cách liên tiếp. Một phương thức gọi lại chính nó được gọi là phương thức đệ quy.
void recursion() { if (condition) { // Điều kiện thoát khỏi đệ quy } recursion(); // Gọi đệ quy }Một hàm đệ quy bao gồm hai phần:
- Phần cơ sở: Điều kiện thoát khỏi đệ quy. Hàm đệ quy không thể gọi tới nó mãi, cần phải có một điểm dừng gọi là điểm neo.
- Phần đệ quy: Thân hàm có chứa lời gọi đệ quy.
Dưới đây là một ví dụ về đệ quy trong Java:
public class RecursionExample { static int count = 0; static void welcome() { count++; if (count = 5) { // Phần cơ sở: Điều kiện thoát khỏi đệ quy System.out.println(count + ". Welcome to gpcoder.com "); welcome(); // Phần đệ quy: Thân hàm có chứa lời gọi đệ quy } } public static void main(String[] args) { welcome(); } }Kết quả:
1. Welcome to gpcoder.com 2. Welcome to gpcoder.com 3. Welcome to gpcoder.com 4. Welcome to gpcoder.com 5. Welcome to gpcoder.com Khi một hàm được gọi, nó sẽ được đưa vào stack. Tương tự, trong đệ quy, mỗi lần gọi chính nó sẽ được đưa vào stack. Nếu không có điểm dừng hoặc gọi mãi mà không tới điểm dừng, sẽ dễ xảy ra tình trạng tràn bộ nhớ stack (java.lang.StackOverflowError).
Dưới đây là ví dụ sử dụng đệ quy với vòng lặp vô tận:
public class RecursionExample { static void welcome() { System.out.println("Welcome to gpcoder.com"); welcome(); // Gọi đệ quy } public static void main(String[] args) { welcome(); } }Kết quả:
Welcome to gpcoder.com Welcome to gpcoder.com Welcome to gpcoder.com Welcome to gpcoder.com Welcome to gpcoder.com Welcome to gpcoder.com Exception in thread "main" java.lang.StackOverflowErrorThiết kế giải thuật đệ quy
Để thiết kế một giải thuật đệ quy, ta cần thực hiện 3 bước sau:
- Tham số hóa bài toán: Xác định các biến và tham số cần thiết cho bài toán.
- Phân tích trường hợp chung: Đưa bài toán về các bài toán nhỏ hơn, có cùng loại với bài toán ban đầu. Dần dần tiến tới trường hợp suy biến.
- Tìm trường hợp suy biến: Xác định trường hợp đặc biệt khi bài toán không còn chia nhỏ được nữa.
Ưu và nhược điểm của đệ quy
Ưu điểm của đệ quy:
- Code gọn ràng, dễ hiểu.
- Giảm độ phức tạp, đặc biệt trong việc giải quyết các vấn đề dựa trên cấu trúc cây.
Nhược điểm của đệ quy:
- Không tối ưu về mặt thời gian (so với sử dụng vòng lặp).
- Gây tốn bộ nhớ.
Một số loại đệ quy
- Đệ quy tuyến tính (Linear Recursion): Mỗi lần thực thi chỉ gọi đệ quy một lần. Ví dụ: Bài toán tính giai thừa, dãy Fibonacci.
- Đệ quy nhị phân (Binary Recursion): Mỗi lần thực thi có thể gọi đệ quy 2 lần. Ví dụ: Bài toán tháp Hà Nội, tính tổ hợp chập K của N.
- Đệ quy lồng (Nested Recursion): Tham số trong lời gọi đệ quy là một lời gọi đệ quy khác. Đệ quy lồng chiếm bộ nhớ rất nhanh. Ví dụ: Hàm số Ackermann.
- Đệ quy hỗ tương (Mutual Recursion): Các hàm gọi đệ quy lẫn nhau. Ví dụ: Xét tính chẵn lẻ của một số nguyên dương bằng đệ quy.
- Quay lui (Backtracking): Trong lập trình, quay lui là một chiến lược giải bài toán một cách đầy đủ nhất, đảm bảo đủ mọi trường hợp bằng phương pháp thử và sai (Try and Error). Quay lui thử tất cả các tổ hợp có thể có để đạt được lời giải cuối cùng. Ví dụ: Bài toán N-Hậu (N-Queen).
Một số chương trình sử dụng đệ quy
Bài toán tính giai thừa
Cho n là một số tự nhiên (n >= 0). Hãy tính giai thừa của n (n!) biết rằng 0! = 1 và n! = (n-1)! * n.
Phân tích: Theo giả thiết, ta có:
- Để tính n!, ta cần tính (n-1)!.
- Để tính (n-1)!, ta cần tính (n-2)!.
- ...
Cài đặt trong Java:
public class RecursionExample { public static long factorial(int n) { if (n == 0) { // Điều kiện thoát khỏi đệ quy return 1; } return n * factorial(n - 1); // Gọi đệ quy } public static void main(String[] args) { System.out.println("Factorial of 5 is: " + factorial(5)); // 120 } }Dãy Fibonacci
Dãy Fibonacci là dãy vô hạn các số tự nhiên. Số Fibonacci thứ n, ký hiệu F(n), được định nghĩa như sau:
- F(1) = 1
- F(2) = 1
- F(n) = F(n-1) + F(n-2) (n >= 3)
Yêu cầu: Tính số Fibonacci thứ n với n cho trước.
Phân tích:
- Với n 3: ta có kết quả là 1.
- Với n >= 3:
- Để tính F(n), ta cần tính F(n-1) và F(n-2).
- Để tính F(n-1), ta cần tính F(n-2) và F(n-3).
- ...
- Cứ như vậy, cho đến khi n = 1 và n = 2.
Cài đặt trong Java:
public class RecursionExample { public static long fibonacci(int n) { if (n 3) { // Điều kiện thoát khỏi đệ quy return 1; } return fibonacci(n - 1) + fibonacci(n - 2); // Gọi đệ quy } public static void main(String[] args) { for (int i = 0; i 10; i++) { System.out.println("fibonacci(" + i + ") = " + fibonacci(i)); } } }Kết quả:
fibonacci(0) = 1 fibonacci(1) = 1 fibonacci(2) = 1 fibonacci(3) = 2 fibonacci(4) = 3 fibonacci(5) = 5 fibonacci(6) = 8 fibonacci(7) = 13 fibonacci(8) = 21 fibonacci(9) = 34Bài toán "Tháp Hà Nội" (Tower of Hanoi)
Đây là một bài toán rất nổi tiếng và kinh điển, rất thích hợp để minh họa cho thuật toán đệ quy. Bài toán có nội dung như sau:
Có 3 cọc được đánh dấu lần lượt là A, B, C và n chiếc đĩa. Các đĩa này có kích thước khác nhau và mỗi đĩa đều có một lỗ ở giữa để cắm vào cọc. Ban đầu, các đĩa đều nằm ở cọc A, trong đó, đĩa nhỏ luôn nằm trên đĩa lớn hơn.
Yêu cầu: Chuyển n đĩa từ cọc A sang cọc đích C với các điều kiện sau:
- Mỗi lần chỉ chuyển được 1 đĩa.
- Trong quá trình chuyển, đĩa nhỏ phải luôn nằm trên đĩa lớn hơn.
- Cho phép sử dụng cọc B làm cọc trung gian.
Phân tích: Ta sẽ xét các trường hợp của n
- Trường hợp đơn giản nhất, n = 1: ta chỉ cần chuyển 1 đĩa từ cọc A sang cọc C.
- Trường hợp n = 2: ta chuyển đĩa nhỏ nhất sang cọc B, chuyển đĩa còn lại sang cọc C, và cuối cùng chuyển đĩa nhỏ ở cọc B sang cọc C.
- Bây giờ ta xét n đĩa (n > 2). Giả sử ta đã có cách chuyển n - 1 đĩa từ một cọc sang một cọc khác. Như vậy, để chuyển n đĩa từ cọc nguồn sang cọc đích, ta cần chuyển n - 1 đĩa từ cọc nguồn sang cọc trung gian. Sau đó chuyển đĩa lớn nhất từ cọc nguồn sang cọc đích. Cuối cùng, chuyển n - 1 từ cọc trung gian về cọc đích.
Cài đặt trong Java:
public class RecursionExample { public static void towerOfHanoi(int n, char source, char destination, char auxiliary) { if (n == 1) { System.out.println(String.format("Chuyen 1 dia tu %s sang %s", source, destination)); } else { towerOfHanoi(n - 1, source, auxiliary, destination); System.out.println(String.format("Chuyen 1 dia tu %s sang %s", source, destination)); towerOfHanoi(n - 1, auxiliary, destination, source); } } public static void main(String[] args) { towerOfHanoi(5, 'A', 'C', 'B'); } }Kết quả:
Chuyen 1 dia tu A sang C Chuyen 1 dia tu A sang B Chuyen 1 dia tu C sang B Chuyen 1 dia tu A sang C Chuyen 1 dia tu B sang A Chuyen 1 dia tu B sang C Chuyen 1 dia tu A sang C Chuyen 1 dia tu A sang B Chuyen 1 dia tu C sang B Chuyen 1 dia tu C sang A Chuyen 1 dia tu B sang A Chuyen 1 dia tu C sang B Chuyen 1 dia tu A sang C Chuyen 1 dia tu A sang B Chuyen 1 dia tu C sang B Chuyen 1 dia tu A sang C Chuyen 1 dia tu B sang A Chuyen 1 dia tu B sang C Chuyen 1 dia tu A sang C Chuyen 1 dia tu B sang A Chuyen 1 dia tu C sang B Chuyen 1 dia tu C sang A Chuyen 1 dia tu B sang A Chuyen 1 dia tu B sang C Chuyen 1 dia tu A sang C Chuyen 1 dia tu A sang B Chuyen 1 dia tu C sang B Chuyen 1 dia tu A sang C Chuyen 1 dia tu B sang A Chuyen 1 dia tu B sang C Chuyen 1 dia tu A sang CTính tổ hợp chập K của N
Mô tả bài toán: Toán học tổ hợp.
Cài đặt trong Java:
public class RecursionExample { public static int combine(int n, int k) { if (k > n) { return 0; } else if (k == 0 || k == n) { return 1; } else { return (combine(n - 1, k) + combine(n - 1, k - 1)); // Đệ quy nhị phân } } public static void main(String[] args) { System.out.println("combine(10, 2) = " + combine(10, 2)); // 45 } }Hàm số Ackermann
Mô tả bài toán: Hàm số Ackermann.
Cài đặt trong Java:
public class Ackermann { public static int ackermann(int x, int y) { if (x == 0) { return (y + 1); } else { if (y == 0) { return ackermann(x - 1, 1); } else { return ackermann(x - 1, ackermann(x, y - 1)); // Đệ quy lồng } } } public static void main(String[] args) { System.out.println("ackerman(3, 2) = " + ackermann(3, 2)); // 29 } }Xét tính chẵn lẻ của một số nguyên dương bằng đệ quy
Mô tả bài toán: Nhập một số nguyên dương n bất kỳ. Kiểm tra số đó là chẵn hay lẻ bằng đệ quy.
Cài đặt trong Java:
public class RecursionExample { public static boolean isEven(int n) { if (n == 0) { return true; } else if (n == 1) { return false; } else { return isOdd(n - 1); } } public static boolean isOdd(int n) { if (n == 0) { return false; } else if (n == 1) { return true; } else { return isEven(n - 1); } } public static void main(String[] args) { System.out.println("isOdd(5) = " + isOdd(5)); // true } }Bài toán N-Hậu (N-Queen)
Mô tả bài toán: Đặt N quân hậu lên trên một bàn cờ có kích thước NxN ô, sao cho không quân hậu nào ăn được quân hậu nào. Hay nói cách khác là không có hai quân hậu nào trên cùng một hàng, cột hoặc đường chéo.
Cài đặt trong Java:
public class RecursionExample { public static final char QUEEN_SIGN = 'Q'; public static final char BLANK_SIGN = '-'; public static final int N = 8; // Set a board with all Blank public static void setBoardBlank(char board[][]) { for (int i = 0; i N; i++) { for (int j = 0; j N; j++) { board[i][j] = BLANK_SIGN; } } } // Print a board to screen public static void printBoard(char board[][]) { for (int i = 0; i N; i++) { for (int j = 0; j N; j++) { System.out.print(board[i][j]); } System.out.println(); } } // Check Queen if at position [RowIndex][ColumIndex] is Safe or not public static boolean isQueenSafeAtPosition(char board[][], int rowIndex, int columnIndex) { // Check safe at Row and Column for (int i = 0; i N; i++) { if (board[rowIndex][i] == QUEEN_SIGN) { return false; } if (board[i][columnIndex] == QUEEN_SIGN) { return false; } } // Check safe at first diagonal for (int i = rowIndex, j = columnIndex; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == QUEEN_SIGN) { return false; } } for (int i = rowIndex, j = columnIndex; i N && j N; i++, j++) { if (board[i][j] == QUEEN_SIGN) { return false; } } // Check safe at second diagonal for (int i = rowIndex, j = columnIndex; i >= 0 && j N; i--, j++) { if (board[i][j] == QUEEN_SIGN) { return false; } } for (int i = rowIndex, j = columnIndex; i N && j >= 0; i++, j--) { if (board[i][j] == QUEEN_SIGN) { return false; } } return true; } // Solve N-Queen Problem, Backtracking here! public static boolean solveNQueenProblem(char board[][], int rowIndex) { if (rowIndex >= N) { return true; } for (int j = 0; j N; j++) { if (isQueenSafeAtPosition(board, rowIndex, j) == true) { board[rowIndex][j] = QUEEN_SIGN; if (solveNQueenProblem(board, rowIndex + 1) == true) { return true; } else { board[rowIndex][j] = BLANK_SIGN; } } } return false; } public static void main(String[] args) { char board[][] = new char[N][N]; setBoardBlank(board); if (solveNQueenProblem(board, 0) == false) { System.out.println("Can't find any solution!"); } else { printBoard(board); } } }Kết quả:
-Q------ -----Q-- -------Q -Q------ ----Q--- ------Q- ---Q---- -Q------ Tài liệu tham khảo: