Nơi căn tủ nhỏ ở phòng khách nhà tôi, có bày một con búp bê Matryoshka nhỏ nhắn với những nét vẽ mềm mại, đáng yêu. Khi còn nhỏ tôi thường đem ra khoe với chúng bạn và đố xem sâu trong thân búp bê mẹ, sẽ là bao nhiêu búp bê con khác. Con búp bê Matryoshka vẫn còn đó, nom trông cũ đi nhiều, nhưng sự thích thú của tôi lại không hề giảm. Giờ, thay vì đem ra nghịch chơi, tôi lại lấy nó làm ví dụ cho một khái niệm rất căn bản trong bất kỳ ngôn ngữ lập trình nào – khái niệm “đệ quy”.
Trong bài dịch này ta hãy cùng tìm hiểu về các đặc điểm của đệ quy và học cách sử dụng đệ quy để giải quyết vấn đề với ngôn ngữ lập trình Java.
1. Hiểu đơn giản đệ quy là gì?
Trước tiên ta cần hiểu phương thức trước, trong lập trình, phương thức là tập hợp các lệnh với tham số truyền vào để máy tính thao tác lệnh theo ý muốn của người viết, đệ quy xảy ra khi người viết các phương thức tự gọi [hoạc định nghĩa lại] chính nó.
Xem ví dụ đơn giản sau nhé. Đề bài: Tính lũy tiến từ 0 đến n.
public int sum[int n] {
if [n >= 1] {
return sum[n - 1] + n;
}
return n;
}
Giải thích:
- Bạn truyền một tham số n vào phương thức sum[], lệnh trong phương thức sum sẽ trả về tham số n bạn truyền vào khi chạy hết chương trình “return n”.
- Để đến được bước đó, chương trình sẽ chạy qua các lệnh điều kiện “if[n>=1]” để định nghĩa lại phương thức sum một lần nữa “sum[n-1] + n”, phương thức mới sẽ khiến giá trị n sẽ thay đổi theo từng vòng của điều kiện cho đến khi không còn thỏa mãn điều kiện được cho.
- Khi chương trình “return n” thì n chính là giá trị đã được tính ở phương thức ta đặt điều kiện bên trên.
Như vậy, hai yếu tố cần để tiến hành một phương thức đệ quy là:
- Có điều kiện dừng: Xác định quy luật của phương thức và tìm giá trị cụ thể khi thỏa mãn một điều kiện nhất định, ở bước này vẫn chưa có phương thức đệ quy nào được gọi.
- Phương thức đệ quy: Phương thức đệ quy sẽ gọi lại chính nó cho đến khi nó trả về điều kiện dừng ở bước 1.
Tưởng tượng, mỗi lần bạn sử dụng đệ quy, chương trình chạy một vòng và bộ nhớ Stack sẽ được chồng thêm một lớp dữ liệu, tình trạng lãng phí bộ nhớ rất dễ xảy ra nếu bạn không phân tích kỹ các vòng chạy đệ quy để có tính toán hợp lý. Vấn đề trên có thể giải quyết bằng cách “tối ưu hóa đòn bẩy đệ quy đuôi”.
2. Đệ quy đuôi và đệ quy đầu
Vậy câu hỏi đặt ra là đệ quy đuôi khác với đệ quy đầu ở đâu. Chúng ta gọi là đệ quy đuôi khi phương thức đệ quy được đặt ở cuối, sau khi chương trình chạy qua điều kiện dừng. Còn lại thì ta gọi đó là đệ quy đầu. Ví dụ, phương thức ở phần 2 là đệ quy đầu, giờ hãy cùng tiếp tục biến đổi một chút và ta có phương thức đệ quy đuôi tính lũy tiến từ currentSum đến n:
public int tailSum[int currentSum, int n] {
if [n