Đệ quy trong Java có vai trò quan trọng trong ngôn ngữ lập trình Java. Sử dụng đệ quy giúp cho nội dung phần code trở nên chặt chẽ hơn. Tuy nhiên nó sẽ khó để hiểu hơn.
Mời bạn đọc tìm hiểu nội dung chi tiết liên quan đến đệ quy khi học Java thông qua nội dung bài viết dưới đây.
Mục lục bài viết
Cú pháp của đệ quy
returntype methodname() { // code methodname();} Tính đệ quy trong Java
Giai thừa của một số, N, được định nghĩa là tích của các số từ 1 đến N. Tức là N! = 1 * 2 * 3 *… N.
Một cách đơn giản để tính giai thừa là sử dụng vòng lặp for. Trong đó tạm thời được khởi tạo thành 1, sẽ phải bắt đầu tăng bộ đếm lên đến N và theo dõi sản phẩm. Vào cuối các lần lặp, dấu tạm thời mang kết quả là giai thừa của N.
Tuy nhiên, một định nghĩa toán học tương đương và chính xác khác của hàm giai thừa đang sử dụng ký hiệu đệ quy; tức là N! = (N-1)! * N.
Nếu bạn muốn tính giai thừa của N, N !, và bạn biết giai thừa của (N-1), (N-1) !, thì đây là cách bạn có thể tính giai thừa của N.
Rõ ràng là cách viết nó như một chương trình theo cách lặp lại và đệ quy trong Java sẽ giống như các quy trình Demo.factorial () và class Factorial.
Mỗi chương trình cung cấp một cách tiếp cận khác nhau để viết đệ quy trong Java – một chương trình sử dụng hàm tĩnh cổ điển, chương trình khác sử dụng thành viên lớp, được kế thừa từ một lớp cơ sở thực hiện chiến lược đệ quy.
Danh sách mã đệ quy trong Java
class Demo {
public static void main(String [] args) {
Rec r = new Rec(5);
System.out.println("Iterative");
r.start_iterative();
System.out.println("Recursive");
r.start_recursive();
Factorial fr = new Factorial(5);
System.out.println("Iterative");
fr.start_iterative();
System.out.println("Recursive");
fr.start_recursive();
System.out.printf(" 1! = %d, 2! = %d, 10! = %d \n",
Demo.factorial(1), Demo.factorial(2), Demo.factorial(10));
}
public static int factorial(int N) {
if ( N == 1 )
return 1;
return Demo.factorial( N -1 )* N;
}
}
class Rec{
int stop;
public Rec(int s){
this.stop = s;
}
public Rec() {
this.stop = 0;
}
public void start_iterative() {
for( int i = 0; i < this.stop; i++) {
System.out.println("Hello world "+Integer.toString(i));
}
}
public void start_recursive(int limit) {
if ( limit <= this.stop ) {
System.out.println("Hello world "+Integer.toString(limit));
this.start_recursive( limit + 1);
}
}
public void start_recursive( ) {
this.start_recursive( 0 );
}
}
class Factorial extends Rec {
int rec_temp;
public Factorial(int s){
this.stop = s;
}
public void start_iterative() {
int val = 1;
for( int i = 1; i <= this.stop; i++) {
val = val*i;
}
System.out.printf("Iterative factorial for %d = %d \n",this.stop, val);
}
public void start_recursive(int val, int result) {
if ( val == 1 ) {
System.out.printf("Recursive factorial %d = %d \n",this.stop, result);
return;
} else {
this.start_recursive( val - 1, result*(val) );
}
}
public void start_recursive( ) {
this.start_recursive( this.stop, 1 );
}
}
Biên soạn chương trình đệ quy trong Java
Lệnh biên soạn chương trình đệ quy được thực hiện như sau:
all:
javac rec.java
java Demo
Trong đó:
javac rec.java: là lệnh để biên dịch mã và sau đó chạy chương trình
java Demo: Kết quả hiển thị
Iterative
Iterative factorial for 5 = 120
Recursive
Recursive factorial 5 = 120
1! = 1, 2! = 2, 10! = 3628800
Ví dụ về đệ quy trong java
Ví dụ 1: vòng lặp vô tận
|
1
2
3
4
5
6
7
8
9
10
|
public class RecursionExample1 { static void p() { System.out.println("hello"); p(); } public static void main(String[] args) { p(); }} |
Kết quả:
hello
hello
...
Exception in thread "main" java.lang.StackOverflowError
Ví dụ 2: vòng lặp có hạn
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class RecursionExample2 { static int count = 0; static void p() { count++; if (count <= 5) { System.out.println("hello " + count); p(); } } public static void main(String[] args) { p(); }} |
Kết quả:
hello 1
hello 2
hello 3
hello 4
hello 5
Ví dụ 3: tính giai thừa
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public class RecursionExample3 { static int factorial(int n) { if (n == 1) return 1; else return (n * factorial(n - 1)); } public static void main(String[] args) { System.out.println("Giai thừa của 5 là: " + factorial(5)); }} |
Kết quả:
Giai thừa của 5 là: 120
Chương trình trên hoạt động như sau:
|
1
2
3
4
5
6
7
8
9
10
|
factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 return 5*24 = 120 |
Ví dụ 4: dãy số Fibonacci
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class RecursionExample4 { static int n1 = 0, n2 = 1, n3 = 0; static void printFibo(int count) { if (count > 0) { n3 = n1 + n2; n1 = n2; n2 = n3; System.out.print(" " + n3); printFibo(count - 1); } } public static void main(String[] args) { int count = 15; System.out.print(n1 + " " + n2); // in 0 và 1 printFibo(count - 2);// n-2 vì 2 số 0 và 1 đã được in ra }} |
Kết quả như sau:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377
Lưu ý khi sử dụng đệ quy trong Java
- Điều kiện kết thúc: Nếu điều kiện kết thúc của bạn không được đặt chính xác, bạn có thể gặp phải vấn đề về đệ quy vô hạn. Và chương trình của bạn có thể hết dung lượng ngăn xếp.
- Các hàm đệ quy lẫn nhau: Các hàm đệ quy gọi nhau, tức là các hàm đệ quy lẫn nhau, rất mạnh trong lập trình máy tính. Chúng được sử dụng trong tất cả các loại từ trình phân tích cú pháp và trình biên dịch để thiết kế các mẫu như khách truy cập
- Sử dụng tài nguyên của các hàm đệ quy: Chi phí tính toán theo không gian và thời gian của các hàm đệ quy có thể cao hơn đáng kể. Mặc dù có thể dễ dàng viết các hàm đệ quy nhưng chúng tiêu tốn rất nhiều không gian ngăn xếp và đôi khi bạn có thể phải chọn một thuật toán lặp lại tương đương.
Tổng kết
Như vậy thông qua bài viết trên đây, Box.edu đã cùng bạn tìm hiểu về đệ quy trong Java. Chúng tôi hy vọng những kiến thức trên sẽ hữu ích đối với bạn.
