Top Ad unit 728 × 90

Latest news

recent

Đệ quy (Recursive) và Vòng lặp (Loop)

Những khái niệm mang tính kinh điển, tuy nhiên vẫn như Bioz thường nói, không có kiến thức nhỏ hay khái niệm lớn trong học thuật. Đôi khi bạn có thể thành chuyên gia, thành công chỉ bằng cách nghiên cứu thuần thục về đệ quy (Recursive) và sử dụng nhuần nhuyễn vòng lặp (Loop).
Trước khi đi vào vấn đề mang tính máy móc, tôi muốn chúng ta nhìn nhận các khái niệm này một cách con người. Hãy xem xét sự khác biệt giữa hai phương thức tư duy đệ quy và lặp. Ngay từ trong từ ngữ ta dễ dàng cảm nhận ra đệ quy là sự lần mò đào sâu vào vấn đề (problem) bằng cách quay lại tìm hiểu những bước, nội dung có liên quan, có ý nghĩa cấu thành của vấn đề ở phía trước, phía ngoài, phía trên theo quan hệ thời gian, bước, lồng ghép hay phân nhánh. Sau khi đã tường tận tới ngọn ngành rồi thì những thông tin đó sẽ giúp ta quay trở lại từ từ theo đường củ và lần lượt tìm ra lời giải ta đang cần. Nếu như trong đệ quy, người ta phân tích vấn đề theo xu hướng truy gốc gác từ cao tới thấp, từ phức tạp tới đơn giản, từ sau ra trước, tới khi nào thông tin rỏ ràng không còn truy được nữa rồi quay lại giải quyết tuần tự vấn đề cho tới khi tìm lại lời giải cuối cùng thì lối suy nghĩa lặp lại có khuynh hướng rã vấn đề theo các phần có giá trị như nhau, ngang hàng, từ đó lắp ghép các vấn đề nhỏ nhằm giải quyết vấn đề lớn.
Để làm rỏ hơn ta sẽ đi vào xem xét một ví dụ rất quen thuộc, tính giai thừa của một số nguyên dương n. Theo định nghĩa thì giai thừa của một số nguyên không âm bằng tích của các số nguyên dương nhỏ hơn hay bằng n (lưu ý: 0! = 1). Như vậy nếu theo suy nghĩ thông thường của định nghĩa, kết quả cần tính dựa vào các giá trị nguyên không âm tuần tự, độc lập nhỏ hơn hay bằng n thể hiện qua công thức:


Khi đó hàm tính toán chỉ đơn giản là một vòng lặp để tuần tự tính tích các phần tử như sau:

unsigned int VnSUtiFactN(unsigned int iUIN)
{
         unsigned int uIResult = 1;
         unsigned int uII = 0;
         if(iUIN != 0)
         {
                for(uII = 1; uII <= iUIN; uII ++)
                {
                       uIResult = uIResult  *  uII;
                }
         }
         return uIResult;
}

Tuy nhiên với cùng một vấn đề đôi khi người ta lại có những cách cảm nhận và suy nghĩ khác hơn, trong trường hợp này cũng vậy, nếu bạn suy nghĩ vấn đề theo lối phân tích đệ quy thì bạn lại mô hình nó theo công thức:

Khi đó hàm tính toán sẽ có phần ngắn hơn nhưng hàm chứa nhiều ý nghĩa hơn thay vì rỏ ràng, trần trụi như cách diễn đạt ở trên.

unsigned int VnSUtiFactN(unsigned int iUIN)
{
          if (iUIN <= 1)
          {
                return 1;
          }else {
                return iUIN * VnSUtiFactN(iUIN - 1);
          }
}

Từ những phân tích logic đã nói ở trên, quá trình tiến hành phân tích giải quyết vấn đề một cách đệ quy phải đi kèm với lưu vết các giá trị, quá trình xử lí, để sau khi tìm ra thông tin cuối cùng còn biết đường quay trở lại lần ngược ra lời giải. Đồng thời Số lần gọi hàm của xử lý là rất lớn, do vậy xử lý đệ quy thường cho tốc độ chậm và chiếm lượng bộ nhớ rất đáng kể so với các xử lý lặp tương đương mà dễ gây ra các vấn đề như thiếu bộ nhớ, quá tải xử lý. Quá trình đệ quy tiếp cận vấn đề một cách khúc chiết nhưng trừu tượng do vậy không dễ mà thực hiện debug chương trình và đôi khi gây khó khăn cho những người mới để hiểu luồng họat động của chương trình. Và cuối cùng, theo "lý thuyết", mọi xử lý đệ quy đều có thể diễn dịch dưới tư duy lặp, tuy nhiên có rất nhiều trường hợp ứng dụng người ta gặp trở ngại lớn trong quá trình triển khai dùng vòng lặp và đệ quy vẫn được trọng dụng.


Binh Nguyen - Bioz 
Đệ quy (Recursive) và Vòng lặp (Loop) Reviewed by Bioz Nguyen on 12:16:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.