Đệ quy Java

Đệ quy Java

Đệ quy là kỹ thuật tự thực hiện một lời 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 với nó.

Ví dụ đệ quy

Việc cộng hai số với nhau rất dễ thực hiện, nhưng thêm một dãy số thì phức tạp hơn. Trong ví dụ sau, đệ quy được sử dụng để cộng một dải số với nhau bằng cách chia nhỏ nó thành tác 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;
    }
  }
}

Giải thích ví dụ

Khi sum()hàm được gọi, nó sẽ thêm tham số kvào tổng của tất cả các số nhỏ hơn kvà 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 kbằng 0 nên chương trình dừng ở đó và trả về kết quả.

Điều kiện tạm dừng

Cũ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 đề về đệ 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 tạm 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 tạm dừng là khi tham số ktrở thành 0.

Sẽ rất hữu ích nếu bạn 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ải số từ đầu đến cuối. Điều kiện tạm 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;
    }
  }
}