Mục lục
Trong Java, một hàm tự gọi nó được gọi là hàm đệ quy. Và, quá trình này được gọi là đệ quy.
Đệ 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.
Đệ quy hoạt động như thế nào?
Trong hình trên, chúng ta gọi hàm recurse từ hàm main. Sau đó, hàm recurse tự gọi lại chính nó mô tả quá trình một method gọi đệ quy.
Để quá trình gọi đệ quy này kết thúc, chúng ta cần cung cấp một số câu điều kiện bên trong hàm, nếu không quá trình này sẽ lặp vô tận.
Bài toán đệ quy điển hình – giai thừa
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.
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 Factorial {
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 + " factorial = " + result);
}
}
Output
4 factorial = 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.
Ưu và nhược điểm của đệ quy
Quá trình gọi đệ quy liên tục, với mỗi lần hàm đệ quy được gọi thì một vùng nhớ được cấp phát cho nó trong stack memory. Cho phép khi chúng trả về kết quả thì vùng nhớ này mới được xoá ra khởi stack. Do đó đệ quy thường chiếm nhiều bộ nhớ.
Mặt khác, giải quyết bài toán bằng phương pháp đệ quy có thể viết code đơn giản và tốn ít thời gian hơn.
Nguồn