Đệ quy trong Java (bất kỳ ngôn ngữ lập trình nào)

Khi làm các dự án thực tế, có khi nào các bạn đã xử lý đến việc như tạo menu nhiều cấp hay tạo sơ đồ quản lý tổ chức, tạo quản lý thư mục tree chưa? Nếu đã từng làm thì mình nghĩ răng các bạn đã sử dụng đệ quy trong lập trình rồi, và tất nhiên trong bài viết này. Mình xin chia sẻ đến các bạn đã và chưa biết về biểu thức đệ quy nhé. Hy vọng sẽ giúp các bạn một phần nào đó theo cách trình bày của mình.

Đệ quy là gì?

 

 

Đệ quy trong java là một kỹ thuật lập trình mà bạn có thể sử dụng trong Java hay bất kỳ ngôn ngữ lập trình nào trong đó một phương thức gọi chính nó để giải quyết một số vấn đề. Khi sử dụng kỹ thuật này ta gọi là đệ quyNhiều vấn đề khi các lập trình viên có thể được giải quyết bằng thuật toán đệ quy khi bài toán trở nên đơn giản hơn, code ngắn gọn và dễ hiểu hơn khi ta sử dụng nhiều vòng lặp for.

Như ta tháy ở hình vẽ sơ đồ trên thì:

  1. Base Case:  là nơi lệnh gọi phương thức dừng lại, có nghĩa là chương trình không thực hiện bất kỳ cuộc gọi đệ quy nào tiếp theo hay nói cách khác là điều kiện để dừng lại.
  2. Recursive Case: là nơi phương thức gọi chính nó nhiều lần cho đến khi nó đến base case.
recursiveMethod() {
  // Base Case
  if (base case condition) {
    return some base case value;
  }
  else {
    // Recursive Case
    return (some work and then a recursive call)
  }
}

 

Các ví dụ về đệ quy?

Một trong những ví dụ kinh điển để giới thiệu đệ quy là tính giai thừa của một số nguyên.

Nếu bạn nào đã quên cách tính và giai thừa là như thế nào thì mình sẽ note lại bên dưới.

Giai thừa là một toán tử một ngôi trên tập hợp các số tự nhiên. Cho n là một số tự nhiên dương,”n giai thừa“, ký hiệu n! là tích của n số tự nhiên dương đầu tiên.

Ta có ví dụ như giai thừa của 5 = 5! là 5 x 4 x 3 x 2 x 1 = 12 bởi vì bất kỳ một giố giai thừa nào ta cũng tính theo công thức:

[n! = n*(n-1)*…*3*2*1]

Cách đệ quy để xem xét vấn đề giai thừa là nhận ra rằng giai thừa của bất kỳ số nào cho trước n đều bằng n lần giai thừa của n –1, với điều kiện n lớn hơn 1. Nếu n là 1, giai thừa của n là 1.

Khi sử dụng đệ quy, điều quan trọng nhất ở bất kỳ phương thức đệ quy nào bắt buộc ta phải có một điều kiện kết thúc. Điều kiện kết thúc cho biết khi nào thì phương thức đệ quy ngừng gọi chính nó. Trong trường hợp này, khi n là 1, nó chỉ trả về 1.Nếu không có điều kiện kết thúc, phương thức đệ quy cứ gọi chính nó mãi mãi.

Khi xác định được công thức và điều kiện kết thúc của một biểu thức chính quy ta sẽ thực hiện việc coding:

private static long factorial(int n)
{
    if (n == 1) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

Trên là ví dụ, cũng như khái niệm về đệ quy trong java nói riêng hay trong ngôn ngữ lập trình nói chung, ngoài ví dụ giai thừa sử dụng đệ quy, ta còn có một số chương trình như menu đa cấp, cấu trúc thư mục tree, hay sơ đồ cơ quan của một tổ chức. Việc nắm được, hiểu được biểu thức chính quy giúp các bạn xử lý vấn đề cũng như bài toán dễ dàng hơn đối với thực tiễn.

Hy vọng bài viết về biểu thức chính quy trên giúp các bạn nắm được tổng quan và biết cách áp dụng trong thực tế.

Happy coding! 😋

x