Đệ quy Java

Đệ quy Java

Đệ quy là kỹ thuật thực hiện lệnh gọi hàm. Kỹ thuật này cung cấp một cách để chia các vấn đề phức tạp thành các vấn đề đơn giản dễ giải quyết hơn.

Đệ quy có thể hơi khó hiểu. Cách tốt nhất để tìm ra cách nó hoạt động là thử nghiệm nó.

Ví dụ đệ quy

Việc cộng hai số với nhau rất dễ thực hiện nhưng việc cộng một dãy số lại phức tạp hơn. Trong ví dụ sau, đệ quy được sử dụng để cộng một dãy số lại với nhau bằng cách chia nó thành nhiệm vụ đơn giản là cộng hai số:

 public class Main { public static void main(String[] args) { int result = sum(10); System.out.println(result); } public static int sum(int k) { if (k > 0) { return k + sum(k - 1); } else { return 0; }
  }
}

Ví dụ giải thích

Khi hàm sum() được gọi, nó thêm tham số k vào tổng của tất cả các số nhỏ hơn k và trả về kết quả. Khi k trở thành 0, hàm chỉ trả về 0. Khi chạy, chương trình thực hiện theo các bước sau:

Vì hàm không tự gọi khi k bằng 0 nên chương trình dừng ở đó và trả về kết quả.

Tình trạng tạm dừng

Giống như các vòng lặp có thể gặp phải vấn đề lặp vô hạn, các hàm đệ quy có thể gặp phải vấn đề đệ quy vô hạn. Đệ quy vô hạn là khi hàm không bao giờ ngừng gọi chính nó. Mọi hàm đệ quy phải có một điều kiện dừng, đó là điều kiện mà hàm ngừng gọi chính nó. Trong ví dụ trước, điều kiện dừng là khi tham số k trở thành 0.

Sẽ rất hữu ích khi xem nhiều ví dụ khác nhau để hiểu rõ hơn về khái niệm này. Trong ví dụ này, hàm thêm một dãy số giữa điểm bắt đầu và điểm kết thúc. Điều kiện dừng cho hàm đệ quy này là khi end không lớn hơn start :

 public class Main { public static void main(String[] args) { int result = sum(5, 10); System.out.println(result); } public static int sum(int start, int end) { if (end > start) { return end + sum(start, end - 1); } else { return end; } } }