Computer >> Máy Tính >  >> Lập trình >> Java

Cách sử dụng đệ quy trong Java

Trong lập trình, đệ quy đề cập đến quá trình trong đó một hàm gọi chính nó một cách trực tiếp hoặc gián tiếp. Đệ quy được sử dụng để giải quyết một số vấn đề trong khoa học máy tính.

Ngôn ngữ lập trình Java hỗ trợ tạo các phương thức đệ quy, là các phương thức tự gọi chúng.

Trong hướng dẫn này, chúng ta sẽ thảo luận, có tham chiếu đến các ví dụ, cách hoạt động của đệ quy và cách bạn có thể tạo một hàm đệ quy trong Java. Sau khi đọc hướng dẫn này, bạn sẽ trở thành chuyên gia viết các phương thức đệ quy trong Java.

Phương thức Java

Các phương thức, đôi khi được gọi là các hàm, là các khối mã thực hiện một nhiệm vụ cụ thể. Ví dụ, một phương thức có thể được sử dụng để tính toán tổng của một mảng giá trị hoặc in ra nội dung của một mảng ra bảng điều khiển.

Đây là cú pháp cho một phương thức trong Java:

modifier static returnType methodName (Parameters) {
	// Method body
}

Ví dụ:giả sử bạn muốn tạo một phương thức in ra câu “Hôm nay là thứ Tư! Chúng ta đã đi được nửa tuần! ” vào bảng điều khiển. Bạn có thể làm như vậy bằng cách sử dụng mã này:

class Main {
public static void printItsWednesday() {
	System.out.println("It's Wednesday! We're half-way through the week!");
}

public static void main(String[] args) {
	printItsWednesday();
}
}

Khi chúng tôi gọi phương thức này bằng cách sử dụng printItsWednesday() , phần sau được trả về:

Hôm nay là thứ Tư! Chúng ta đã đi được nửa tuần!

81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia một cuộc thi đào tạo. Kết hợp với bootcamp ngay hôm nay.

Sinh viên tốt nghiệp bootcamp trung bình dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.

Nếu bạn muốn tìm hiểu thêm về các phương thức Java, bạn có thể đọc hướng dẫn đầy đủ của chúng tôi về các phương thức trong Java tại đây.

Trong ví dụ trên, chúng tôi gọi prinItsWednesday() trong chương trình chính. Nhưng nếu chúng ta gọi phương thức của mình trong chính phương thức đó, chúng ta sẽ tạo ra một phương thức đệ quy.

Đệ quy Java

Phương thức đệ quy là các phương thức được gọi bên trong phương thức chính lúc đầu và sau đó được gọi bên trong chính phương thức đó. Đây là cú pháp cho một phương thức đệ quy:

static void executeMethod() {
	// Code here
	executeMethod(); // This is our recursive call
	// Code here
}

public static void main(String[] args) {
	executeMethod(); // This is the normal method call
}

Khi chúng tôi chạy chương trình của mình, executeMethod() phương thức được gọi trong chương trình chính của chúng tôi. Điều này gây ra mã trong executeMethod() phương thức được chạy, trong trường hợp này bao gồm executeMethod() phương pháp. Vì vậy, khi chương trình của chúng ta chạy, nó sẽ đi vào một vòng lặp.

Chương trình sẽ tiếp tục thực thi executeMethod() cho đến khi một điều kiện được đáp ứng để ngăn nó tiếp tục. Nếu không có điều kiện nào được chỉ định có thể dừng đệ quy, chương trình sẽ chạy mãi mãi. Điều này được gọi là đệ quy vô hạn.

Tại sao bạn nên sử dụng đệ quy? Đầu tiên, đệ quy có thể làm giảm độ phức tạp về thời gian của một chương trình trong một số trường hợp nhất định. Thứ hai, đệ quy có thể giúp bạn dễ dàng triển khai một số thuật toán theo cách dễ đọc hơn và dễ bảo trì hơn.

Dưới đây là một vài ví dụ về các chương trình thường được viết bằng cách sử dụng đệ quy:

  • Tính toán chuỗi fibonacci
  • Đảo ngược một chuỗi
  • Tính giai thừa của một số
  • Tính toán chiều cao của cây nhị phân

Điều đó nói rằng, đệ quy có thể chậm hơn so với việc viết một phương thức chuẩn để thực hiện một tác vụ. Điều này là do đệ quy tạo ra một vị trí lưu trữ mới cho các biến mỗi khi một phương thức đệ quy được thực thi.

Ví dụ về đệ quy Java

Hãy xem qua hai ví dụ để chứng minh cách hoạt động của đệ quy trong Java.

Đảo ngược một chuỗi bằng cách sử dụng đệ quy

Giả sử chúng tôi đang xây dựng một chương trình cho giáo viên trung học cơ sở đảo ngược một chuỗi với điểm của mỗi học sinh trong suốt cả năm. Chuỗi bắt đầu bằng điểm đầu tiên mà học sinh nhận được và kết thúc bằng điểm gần đây nhất mà học sinh đó đã kiếm được. Chúng tôi muốn đảo ngược chuỗi để điểm cuối cùng hoặc gần đây nhất mà học sinh kiếm được sẽ nằm đầu tiên trong chuỗi.

Chúng tôi có thể sử dụng mã sau để đảo ngược chuỗi:

public class ReverseGrades {
	public static String reverse(String grades) {
		if (grades.isEmpty())
			return grades;
		return reverse(grades.substring(1)) + grades.charAt(0);
	}

	public static void main(String[] args) {
		String grades = "CBCBAABACAABA";
		String reverse_grades = reverse(grades);

		System.out.println("This student's grades for the year are: " + reverse_grades);
	}
}

Mã của chúng tôi trả về:

Điểm của học sinh này trong năm là:ABAACABAABCBC

Như bạn có thể thấy, chương trình của chúng tôi đã đảo ngược nội dung trong chuỗi của chúng tôi. Trong chương trình của chúng tôi, chúng tôi đã tạo một hàm đệ quy có tên là reverse() .

Khi reverse() hàm được thực thi, trước tiên hãy kiểm tra xem chuỗi điểm có trống không. Nếu đúng, chúng ta trả lại danh sách các lớp cho chương trình chính. Điều này dừng đệ quy vì reverse() lệnh gọi ở cuối hàm không có cơ hội chạy.

Nếu chuỗi điểm không trống, chương trình của chúng tôi sẽ thực thi reverse() phương thức lại và nối kết quả của hàm với ký tự đầu tiên của câu. Chúng tôi sử dụng charAt() trong ví dụ của chúng tôi để truy xuất ký tự đầu tiên trong câu và thêm nó vào bên trái của reverse() phương pháp.

Sau khi chuỗi của chúng tôi đã được đảo ngược, một thông báo cho biết This student’s grades for the year are: “, Tiếp theo là chuỗi điểm của học sinh được đảo ngược, được quay trở lại chương trình.

Tính giai thừa bằng đệ quy

Một trường hợp khác mà phép đệ quy có thể hữu ích là tính giai thừa của một số.

Trong toán học, thừa số là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng một số nhân với nhau. Ví dụ:giai thừa của 5 bằng 5 * 4 * 3 * 2 * 1, là 120. Bởi vì các phương pháp giai thừa liên quan đến một phép tính lặp lại, chúng là một ví dụ thực tế tốt về nơi mà đệ quy có thể hữu ích trong việc giải quyết một vấn đề .

Chương trình Java sau đây cho phép chúng ta tính giai thừa của số 7 trong Java:

class Main {
	static int calculateFactorial(int number) {
		if (number != 0)
			return number * calculateFactorial(number-1);
		else
			return 1;
	}
	
	public static void main(String[] args) {
		int num = 7;
		int answer = calculateFactorial(num);
		System.out.println("The factorial of 7 is: " + answer);
	}
}

Mã của chúng tôi trả về:

The factorial of 7 is: 5040

Trong ví dụ này, chúng tôi tạo một phương thức có tên là calculateFactorial() nhân số được lưu trữ trong tham số số với kết quả của calculateFactorial() tiếp theo phương pháp. Quá trình này thực hiện cho đến khi tham số number bằng 0.

Khi tham số number bằng 0, câu lệnh if trong mã của chúng ta trả về 1 và kết quả của calculateFactorial() phương thức được chuyển trở lại chương trình chính.

Vì vậy, calculateFactorial() phương thức thực hiện 7 * 6 * 5 * 4 * 3 * 2 * 1, sau đó trả về câu trả lời cho chương trình chính. Khi câu trả lời đã được tính toán, thông báo The factorial of 7 is: , theo sau là câu trả lời do chương trình của chúng tôi tính toán, được in ra bảng điều khiển.

Kết luận

Đệ quy là một khái niệm trong lập trình dùng để mô tả một phương thức gọi chính nó. Phương thức đệ quy có thể hữu ích trong trường hợp bạn cần lặp lại một tác vụ nhiều lần và sử dụng kết quả của lần lặp trước đó của tác vụ đó trong lần lặp hiện tại.

Hướng dẫn này đã trình bày những kiến ​​thức cơ bản về đệ quy trong Java và cách tạo các phương thức đệ quy. Ngoài ra, hướng dẫn này đã trình bày qua hai ví dụ về đệ quy trong hoạt động, liên quan đến việc đảo ngược một chuỗi và tính giai thừa.

Bây giờ, bạn đã sẵn sàng để bắt đầu làm việc với các phương thức đệ quy trong Java như một người chuyên nghiệp!