Giải Thuật Đệ Quy trong Java – GP Coder (Lập trình Java)

Đệ quy là gì?

Đệ quy (Recursion) là một trong những giải thuật khá quen thuộc trong lập trình, mở rộng ra là trong toán học (thường được gọi với tên khác là “quy nạp”). Có một số bài toán, buộc phải sử dụng đệ quy mới giải quyết được, chẳng hạn như duyệt cây.

Một bài toán mang tính chất đệ quy khi nó có thể được phân rã thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn nữa. Cứ tiếp tục như thế cho đến khi không thể chia nhỏ được được hoặc đạt được kết quả mong muốn.

Đệ quy trong Java

Đệ quy trong Java là quá trình trong đó 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 trong java 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
}

Thành phần của một hàm đệ quy:

  • 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 (còn gọi là điểm neo) tại một trường hợp đặc biệt, gọi là trường hợp suy biến (degenerate case).
  • Phần đệ quy: Thân hàm có chứa lời gọi đệ quy

Ví dụ:

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, hàm đệ quy cũng vậy, mỗi lần gọi chính nó thì nó lại được đưa vào Stack, nếu như không có điểm dừng, hoặc gọi mãi mà chưa tới điểm dừng, sẽ dễ xảy ra tình trạng tràn bộ nhớ Stack (java.lang.StackOverflowError).

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();
    }
 
    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.StackOverflowError

Thiết kế giải thuật đệ quy

Thực hiện 3 bước sau:

  • Tham số hóa bài toán
  • Phân tích trường hợp chung: Đưa bài toán về bài toán nhỏ hơn cùng loại, dần dần tiến tới trường hợp suy biến
  • Tìm trường hợp suy biến

Ưu và nhược điểm của đệ quy

Ưu điểm: một số trường hợp giúp 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: 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. Xem ví dụ: Bài toán tính giai thừa, Dãy Fibonaci.
  • Đệ quy nhị phân (Binary Recursion): mỗi lần thực thi có thể gọi đệ quy 2 lần. Xem 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. Đệ quy lồng chiếm bộ nhớ rất nhanh. Xem ví dụ: Hàm số Ackermann.
  • Đệ quy hỗ tương (Mutual Recursion): Các hàm gọi đệ quy lẫn nhau. Xem 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, có 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).
    • Nét đặc trưng của phương pháp này là ở chỗ các bước đi đến lời giải hoàn toàn bằng cách làm thử. Nếu có một lựa chọn được chấp nhận thì ghi nhớ các thông tin cần thiết các bước thử tiếp theo. Trái lại, nếu không có một lựa chọn nào thích hợp thì làm lại bước trước, xoá bớt các ghi nhớ và quay về chu trình thử với các lựa chọn còn lại. Hành động này được gọi là quay lui (Back tracking) và các giải thuật thể hiện phương pháp này gọi là các giải thuật quay lui.
    • Việc quay lui để thử tất cả các tổ hợp có thể có để đạt được lời giải cuối cùng.
    • Xem 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)! x n.

Phân tích :

Theo giả thiết, ta có : n! = (n-1)! x n. Như vậy :

  • Để tính n! ta cần phải tính (n-1)!
  • Để tính (n-1)! ta phải tính (n-2)!

Cứ như vậy, cho tới khi gặp trường hợp 0!. Khi đó ta lập tức có được kết quả là 1, không cần phải tính thông qua một kết quả trung gian khác.

Cài đặt trên 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 Fibonaci

Dãy Fibonaci là dãy vô hạn các số tự nhiên. Số Fibonaci thứ n, ký hiệu F(n), được định nghĩa như sau :

  • F(n) = 1, nếu n=1 hoặc n=2
  • F(n) = F(n-1) + F(n-2), nếu n>=3

Yêu cầu : tính số fibonaci thứ n với n cho trước.

Phân tích : theo giả thiết

– Với n<3 : ta có kết quả là 1

– Với n>=3 :

  • Đế tính F(n) ta phải tính F(n-1) và F(n-2).
  • Để tính F(n-1) ta lại phải tính F(n-2) và F(n-3), và để tính F(n-2) ta phải tính F(n-3) và F(n-4).
  • Cứ như vậy cho đến khi n=1 và n=2.

Cài đặt trên Java

public class RecursionExample {
	public static long fibonaci(int n) {
		if (n < 3) { // Điều kiện thoát khỏi đệ quy
			return 1;
		}
		return fibonaci(n - 1) + fibonaci(n - 2); // gọi đệ quy
	}

	public static void main(String[] args) {
		for (int i = 0; i < 10; i++) {
			System.out.println("fibonaci(" + i + ") = " + fibonaci(i));
		}
	}

}

Kết quả:

fibonaci(0) = 1
fibonaci(1) = 1
fibonaci(2) = 1
fibonaci(3) = 2
fibonaci(4) = 3
fibonaci(5) = 5
fibonaci(6) = 8
fibonaci(7) = 13
fibonaci(8) = 21
fibonaci(9) = 34

Bài toán “Tháp Hà Nội” (Tower of Ha Noi)

Đâ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. Sau đây là nội dung bài toán :

Có 3 chiếc 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.

– Nhiều hơn một chút, 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 trên Java

public class RecursionExample {
	public static void thapHaNoi(int n, char nguon, char dich, char trungGian) {
	    //điểm neo
	    if (n == 1) {
	    	System.out.println(String.format("Chuyen 1 dia tu %s sang %s", nguon, dich));
	    } else {
	        //chuyển n-1 đĩa từ cọc nguồn sang cọc trung gian,
	        //lấy cọc đích làm cọc phụ
	    	thapHaNoi(n - 1, nguon, trungGian, dich);
	    	
	        //chuyển còn lại từ cọc nguồn sang cọc đích
	        System.out.println(String.format("Chuyen 1 dia tu %s sang %s", nguon, dich));
	        
	        //chuyễn n-1 từ cọc trung gian về cọc đích,
	        //lấy cọc nguồn làm cọc trung gian
	        thapHaNoi(n - 1, trungGian, dich, nguon);
	    }
	}

	public static void main(String[] args) {
		thapHaNoi(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 C

Tí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)); // Binary Recursion
		}
	}

	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)); // Nested Recursion
			}
		}
	}

	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 bất kì nào trên cùng một hàng, một cột hoặc một đườ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 postion [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

5.0

Nếu bạn thấy hay thì hãy chia sẻ bài viết cho mọi người nhé!

Shares

Bình luận

bình luận