09 tháng 11, 2018 – 29444 lượt xemNơi căn tủ nhỏ ở phòng khách nhà tôi, có bày một con búp bê Matryoshka nhỏ xíu với những nét vẽ mềm mại và mượt mà, đá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ú vị 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ơ bản trong bất kể ngôn từ lập trình nào – khái niệm “ đệ quy ” .
Nếu thấy khó hiểu với khái niệm đệ quy, hãy liên tưởng đến búp bê MatryoshkaTrong bài dịch này ta hãy cùng tìm hiểu và khám phá về những đặc thù của đệ quy và học cách sử dụng đệ quy để xử lý yếu tố với ngôn từ 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 thuầ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 để triển khai một phương pháp đệ 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 tài liệu, thực trạng tiêu tốn lãng phí bộ nhớ rất dễ xảy ra nếu bạn không nghiên cứu và phân tích kỹ những vòng chạy đệ quy để có đo lường và thống kê hài hòa và hợp lý. Vấn đề trên hoàn toàn có thể xử lý bằng cách “ tối ưu hóa đòn kích bẩy đệ quy đuôi ” .
Viết code bất cẩn, sẽ có n số khung đệ quy ghi đè lên bộ nhớ Stack
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 pháp đệ quy được đặt ở cuối, sau khi chương trình chạy qua điều kiện kèm theo dừng. Còn lại thì ta gọi đó là đệ quy đầu. Ví dụ, phương pháp ở phần 2 là đệ quy đầu, giờ hãy cùng liên tục biến hóa một chút ít và ta có phương pháp đệ quy đuôi tính lũy tiến từ currentSum đến n :
public int tailSum(int currentSum, int n) { if (n Như vậy với phương pháp đệ quy đuôi, phương pháp đệ quy sẽ được chương trình ưu tiên giải quyết và xử lý dứt điểm. Chương trình sẽ không phải chạy nhiều vòng giải quyết và xử lý điều kiện kèm theo như phương pháp đệ quy đầu, nên theo logic, rủi ro tiềm ẩn tràn bộ nhớ Stack sẽ được giảm thiểu .
3. So sánh giữa đệ quy và vòng lặp
Ưu điểm lớn nhất của phép đệ quy là tiếp cận giải quyết và xử lý yếu tố bằng những đoạn code sạch, ngăn nắp, dễ đọc, dễ hiểu. Nhược điểm rõ ràng là rủi ro tiềm ẩn cao tràn bộ nhớ Stack như đã lý giải ở trên .Cùng xử lý một bài toán nhưng một giải pháp khác để thay thế sửa chữa đệ quy là sử dụng vòng lặp .Đề bài giống với bài toán tính lũy tiến n ở trên, ta có cách xử lý với vòng lặp như sau :
public int iterativeSum(int n) { int sum = 0; if(n Dù vòng lặp có một ưu điểm là chỉ có một vòng duy nhất được gọi ra và ta sẽ không phải lo nghĩ gì về yếu tố tràn bộ nhớ Stack. Nhưng vòng lặp cũng có một điểm yếu kém so với đệ quy là code giải quyết và xử lý sẽ viết dài và phức tạp hơn .
4. Các ví dụ mở rộng của đệ quy
Sức mạnh thật sự của đệ quy là thay vì bạn phải phong cách thiết kế những thuật toán dài dòng với vòng lặp, đệ quy được cho phép ta vận dụng những tư duy toán học trực tiếp vào thuật toán một cách thuận tiện .Đề bài : Nhập giá trị n và tìm đơn vị chức năng của 10 nLũy thừa100101102103…10 n – 110 nĐơn vị1101001000……
…
Để xử lý bài toán, ta thực thi những bước sau :
- Trước tiên phân tích quy luật của bài toán, để tính giá trị của 10n ta sẽ phải tính giá trị của 10n-1 * 10 trước.
- Nhưng để được giá trị của 10n-1 thì ta sẽ phải tính đơn vị 10(n-1)-1 trước.
- Cứ vậy ta xác định được số hai số cuối sẽ là 101 = 10 và 100 = 1. Đây chính là “điều kiện dừng”, khi đã xác định được điều kiện dừng, thì việc còn lại chỉ là thiết kế phương trình đệ quy phù hợp.
- Từ phân tích trên, ta sẽ đưa ra 2 trường hợp với n = 0 và n>0 (đây sẽ là trường hợp ta sử dụng đệ quy).
public int powerOf10(int n) { if (n == 0) { return 1; } return powerOf10(n-1) * 10;
}5. Dãy Fibonacci và đệ quy
Dãy Fibonacci là dãy vô hạn những số tự nhiên mở màn bằng hai thành phần 0 và 1, dãy được thiết lập theo quy tắc mỗi thành phần luôn bằng tổng hai thành phần trước nó, ta có dãy Fibonacci sau : 0 1 1 2 3 5 8 13 21 34 55 …Dãy số Fibonacci0112358……Số thứ tự1234567…nTìm số Fibonacci tương ứng với số thứ tự n, để sử dụng đệ quy tìm được số Fibonacci tương ứng, ta sẽ cần xác lập quy luật và điều kiện kèm theo dừng trước của dãy số Fibonacci .
- Quy luật, ta nhận thấy số n sẽ là tổng của 2 chữ số đứng sau nó là (n-2) + (n-1).
- Và ta biết chắc chắn rằng n1 = 0 và n2= 1 là điều kiện dừng của dãy số.
- Như vậy, ta sẽ chia làm 2 trường hợp và thực hiện phương thức đệ quy như sau:
public int fibonacci(int n) { if (n 6. Biểu diễn số thập phân dưới dạng nhị phân với đệ quy
Thử đặt ra đề bài với trường hợp khi ta muốn chuyển một số ít từ dạng thập phân n sang dạng nhị phân, tựa như như những bước trên ta thực thi :
- Xác định được quy luật của chuyển đổi từ số thập phân sang nhị phân là chia số n cho 2, giữ lại phần dư (0 hoạc là 1), tiếp tục lấy thương chia tiếp cho 2 cho đến khi trở về trường hợp 1 chia cho 2 (0 dư 1).
- Xác định điều kiện dừng của quy luật là khi số n = 0, ta có 0 chia 2 vẫn là 0 và n = 1, 1 chia cho 2 bằng 0 dư 1.
- Như vậy ta chia ra làm 2 trường hợp và thực hiện phép đệ quy như sau:
public String toBinary(int n) {
if (n 7. Kết luận
Đệ quy là một khái niệm căn bản trong lập trình và đầy hiệu quả trong tư duy giải quyết vấn đề. Rất nhiều bài toán sau khi được phân tích có thể được giải quyết bằng đệ quy và đồng thời nhiều bài toán khác nếu tiếp cận với đệ quy sẽ tiết kiệm được rất nhiều đoạn code dài dòng.
Thường xuyên rèn luyện xử lý yếu tố với đệ quy sẽ trợ giúp là rất hữu dụng cho tư duy thuật toán của những lập trình viên mới vào nghề, khi mà họ nên học giải pháp tiếp cận và giải quyết và xử lý yếu tố một cách logic và ngăn nắp nhất hoàn toàn có thể .Lập trình Java cơ bản và nâng caoLập trình Web Java Spring 2018
