Đệ Quy Trong Java | Lập Trình Từ Đầu

1. Đệ quy trong Java là gì?

Đệ quy trong Java – Java Recursion là quá trình mà hàm tự gọi nó trong một thời gian. Nghĩa là sao nghĩa là nó sẽ tự gọi lại chính nó. Một phương thức trong Java gọi lại chính nó được gọi là phương thức đệ quy. Việc sử dụng đệ quy sẽ giúp code ta chặt chẽ hơn, giải được nhiều bài toán hơn nhưng đồng thời đi kèm là code sẽ khó hiểu hơn với những người mới.

Hiểu nôm na thế này đệ quy là phương pháp phân rã bài toán lớn thành các bài toán nhỏ hơn nhưng chúng có cùng tính chất với bài toán lớn ban đầu. Các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn. Cứ tiếp tục như thế cho đến khi không thể chia nhỏ được được hoặc đạt được kết quả mong muốn.

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

2. Cú pháp và điều kiện cơ sở của đệ quy trong Java

Ta có cú pháp của đệ quy như sau:

returntype methodname() { // code methodname(); }

Trong đó methodname() chính là phương thức. Trong methodname() ta lại gọi cùng một phương thức methodname() . Đây chính là phương thức đệ quy. Để dừng lời gọi đệ quy, chúng ta cần cung cấp một số điều kiện bên trong phương thức đó. Nếu không, phương thức sẽ được gọi vô hạn. Do đó, chúng ta sẽ sử dụng câu lệnh if…else (hoặc cách tiếp cận tương tự) để kết thúc lệnh gọi đệ quy bên trong phương thức.

Ví dụ: cộng tất cả các số lên đến 10

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; } } }

Kết quả

55

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. Ý 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. Nó chính là điều kiện để dừng đệ quy. Đệ quy sẽ 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ó.

Với bài toán trên Khi hàm sum() được gọi, nó sẽ 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:

10 + tổng (9) 10 + (9 + tổng (8)) 10 + (9 + (8 + tổng (7))) ... 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + tổng (0) 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

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ả.

Ngoài ra 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.

3. 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.

Ví dụ:

class Main { 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); } }

Kết quả

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.

4. Bài toán đệ quy tính giai thừa trong Java

Đây là một bài toán điển hình hay gặp trong Java. Nó được sử dụng nhiều cho việc học cũng như là những ứng dụng cho sau này.

Ví dụ như giai thừa của một số n (n>= 0) sẽ được tính theo công thức n! = n*n-1*n-2…1. Biết rằng 0! = 1.

Trước hết chúng ta có thể thấy một quy luật rằng n! = (n-1)!*n, mà (n-1)! = (n – 2)!*n-1, cứ như vậy, chúng ta sẽ tổng quát hoá bài toán này bằng đệ quy.

class Main { static int factorial( int n ) { if (n != 0) // điều kiện dừng return n * factorial(n-1); // gọi đệ quy else return 1; } public static void main(String[] args) { int number = 4, result; result = factorial(number); System.out.println(number + " gia thừa bằng " + result); } }

Kết quả

4 gia thừa bằng 24

Phương thức factorial() đang gọi chính nó. Ban đầu, giá trị của n là 4 bên trong factorial() . Trong lần gọi đệ quy tiếp theo, phương thức factorial() sẽ được gọi với giá trị là 3. Quá trình này tiếp tục cho đến khi n bằng 0. Chương trình trên hoạt động như sau:

factorial(4) factorial(3) factorial(2) factorial(1) return 1 return 2*1 = 2 return 3*2 = 6 return 4*6 = 24 5. Một số ví dụ khác về đệ quy trong Java

• Vòng lặp vô tận

public class Main{ static void p() { System.out.println("hello"); p(); } public static void main(String[] args) { p(); } }

Kết quả

hello hello ... Exception in thread "main" java.lang.StackOverflowError

• Vòng lặp có hạn

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; } } }

Kết quả

45

Với ví dụ này ta sử dụng điều kiện tạm dừng cho hàm đệ quy này là khi end không lớn hơn start

• Dãy số Fibonacci

public class Main { static int n1 = 0, n2 = 1, n3 = 0; static void printFibo(int count) { if (count > 0) { n3 = n1 + n2; n1 = n2; n2 = n3; System.out.print(" " + n3); printFibo(count - 1); } } public static void main(String[] args) { int count = 15; System.out.print(n1 + " " + n2); // in 0 và 1 printFibo(count - 2);// n-2 vì 2 số 0 và 1 đã được in ra } }

Kết quả

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377