Đệ quy trong Java - Tìm hiểu về đệ quy cho người mới bắt đầu

Đệ quy là gì?

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 được gọi là đệ quy và hàm tương ứng được gọi là hàm đệ quy. Sử dụng thuật toán đệ quy, các vấn đề nhất định có thể được giải quyết dễ dàng. Ví dụ về các vấn đề như Inorder/ Preorder/ DFS of Graph,...

Một hàm đệ quy bao gồm hai phần là phần cơ sở và phần đệ quy:

Phần cơ sở: Điều kiện thoát khỏi đệ quy. Hàm đệ quy không thể gọi mãi mà cần phải có một điểm dừng ( điểm neo) tại một trường hợp đặc biệt, được gọi là trường hợp suy biến.

Phần đệ quy: Thân hàm có chừa lời gọi đệ quy

>>> Đọc thêm: Lớp trừu tượng trong Java - Nắm vững khái niệm về abstract trong Java

Điều kiện cơ sở trong đệ quy trong Java là gì?

Trong chương trình đệ quy, lời giải cho các trường hợp cơ sở được cung cấp và lời giải cho bài toán lớn hơn được thể hiện dưới dạng nhỏ hơn.

Ví dụ:

int fact(int n)

{

    if (n < = 1) // base case

        return 1;

    else    

        return n*fact(n-1);    

}

Trong ví dụ trên, trường hợp cơ sở cho n<=1 được xác định và giá trị lớn hơn của số có thể được giải quyết bằng cách chuyển đổi thành nhỏ hơn cho đến khi đạt được trường hợp cơ sở.

Làm thế nào một vấn đề được giải quyết bằng cách sử dụng đề quy

Ý tưởng là thể hiện một vấn đề dưới dạng một hoặc nhiều vấn đề nhỏ hơn và thêm một hoặc nhiều điều kiện cơ sở để dừng đệ quy. Ví dụ, chúng ta tính giai thừa n nếu chúng ta biết giai thừa của (n-1). Trường hợp cơ sở cho giai thừa sẽ là n=0. Chúng trả về kết quả là 1 khi n=0.

Sự khác biệt giữa đệ quy trực tiếp và gián tiếp

Một hàm fun được gọi là đệ quy trực tiếp nếu nó gọi hàm fun tương tự. Một hàm fun được gọi là hàm đệ quy gián tiếp nếu nó gọi một hàm khác là fun_new và fun_new sẽ gọi hàm fun một cách trực tiếp hoặc gián tiếp. Sự khác biệt giữa đệ quy trực tiếp hoặc gián tiếp đã được mô tả trong bảng 1. 

Cách bộ nhớ được cấp phát cho lệnh gọi hàm khác nhau trong đệ quy

Khi bất kỳ hàm nào được gọi từ hàm main (), bộ nhớ sẽ được cấp phát cho nó trên ngăn xếp. Một hàm đệ quy tự gọi hàm, bộ nhớ cho hàm được gọi được cấp phát trên bộ nhớ được cấp phát cho hàm gọi và bản sao khác nhau của các biến cục bộ được tạo cho mỗi lệnh gọi hàm. Khi đạt đến trường hợp cơ sở, hàm trả về giá trị của nó cho hàm mà nó được gọi và bộ nhớ được hủy cấp phát và quá trình tiếp tục.

Chúng ta có thể lấy ví dụ về cách hoạt động của đệ quy bằng cách lấy một hàm đơn giản:

/ A Java program to demonstrate

// working of recursion

  class GFG {

    static void printFun(int test)

    {

        if (test < 1)

            return;

          else {

            System.out.printf("%d ", test);

              // Statement 2

            printFun(test - 1);

              System.out.printf("%d ", test);

            return;

        }

    }

      public static void main(String[] args)

    {

        int test = 3;

        printFun(test);

    }

}

Output

3 2 1 1 2 3

Khi printFun(3) được gọi từ hàm main(), bộ nhớ được cấp cho printFun (3) và một bài kiểm tra biến cục bộ được khởi tạo thành 3 và câu lệnh 1 tới 4 được đẩy lên ngắn xếp như được hiển thị trong sơ đồ dưới đây. Đầu tiên nó in “3”. Trong câu lệnh 2, printFun (2) được gọi và bộ nhớ được cấp cho printFun(2) và một  kiểm tra biến cục bộ được khởi tạo thành 2 và câu lệnh 1 đến 4 được đẩy vào ngăn xếp.

Tương tự, printFun (2) gọi printFun(1) và printFun (1) gọi printFun (0). printFun (0) chuyển đến câu lệnh if và nó trở về printFun (1). Các câu lệnh còn lại của printFun(1) được thực thi và nó trở về printFun(2),... Trong đầu ra, giá trị từ 3 đến 1 được in và sau đó từ 1 đến 3 được in. Ngăn xếp bộ nhớ (memory stack) được thể hiện bởi sơ đồ dưới đây:

Ưu và nhược điểm của đệ quy trong Java

Ưu điểm của việc sử dụng chương trình đệ quy thay vì trình lặp trong Java

Đệ quy trong Java cung cấp cách viết mã đơn giản và gọn gàng hơn. Một số bài toán vốn có tính đệ quy, đối với những bài toán như vậy, chúng ta có thể viết các mã như vậy lặp đi lặp lại với sự trợ giúp của cấu trúc dữ liệu ngăn xếp (stack data structure). 

Nhược điểm của Lập trình đệ quy so với trình lặp lại

Bạn cần chú ý rằng cả chương trình đệ quy và trình lặp đều có quyền hạn giải quyết các vấn đề tương tự như nhau, tức là, mọi chương trình đệ quy đều có thể được viết một cách lắp lại và ngược lại mà vẫn đúng. Chương trình đệ quy có yêu cầu không gian lớn hơn trình lặp vì tất cả các hàm sẽ duy trì trong ngắn xếp đến khi đạt được trường hợp cơ sở.

Kết luận: Đệ quy trong Java là một yếu tố lập trình viên cần nắm rõ trong quá trình làm việc với các dự án Java. Hy vọng bài viết trên đã giúp bạn hiểu rõ hơn về đệ quy trong Java. Đừng quên tìm hiểu thêm về Java và các ngôn ngữ lập trình khác qua các khóa học lập trình Viện công nghệ thông tin T3H.