Bài 9: Kỹ Thuật đệ Quy (tiếp Theo) - Phuong's Blog

Bài viết này trình bày về việc phân loại một số dạng đệ quy thường gặp, đưa ra một số ví dụ để các bạn có cái nhìn cơ bản nhất với từng loại.

3. Phân loại đệ quy

3.1. Đệ quy tuyến tính

– Bên trong thân hàm có duy nhất một lời gọi đệ quy. Ví dụ đoạn code tính giai thừa ở bài trước là một hàm đệ quy tuyến tính.

3.2. Đệ quy nhị phân

– Đơn giản là trong thân hàm có 2 lời gọi đệ quy.

– Xét ví dụ đơn giản về hàm tính f(n) của dãy Fibonaci:

• f(0) = f(1) = 1
• f(n) = f(n-1) + f(n-2)

int Fibonaci(int n) { if (n == 0 && n == 1) return 1; else return Fibonaci(n-1) + Fibonaci(n-2); }

3.3. Đệ quy hỗ tương

– Hàm f1 có lời gọi đến hàm f2.

–  Hàm f2 cũng có lời gọi đến hàm f1.

– Xét công thức:

• X(0)=1, Y(0)=1
• X(n) = X(n-1) + Y(n-1)
• Y(n) = X(n-1) * Y(n-1)

int X(int n) { if (n == 0) return 1; else return X(n - 1) + Y(n - 1); } int Y(int n) { if (n == 0) return 1; else return X(n - 1) * Y(n - 1); }

3.4. Đệ quy phi tuyến

– Hàm có lời gọi lại chính nó được đặt trong vòng lặp.

– Ví dụ:

• S(1) = 1
• S(n) = S(1) + S(2) + … + S(n-1)

int S(int n) { if (n == 1) return 1; int res = 0; for (int i = 1; i < n ; i++) res += S(i); return res; }

4. Nhận xét về đệ quy

– Tuỳ vào từng thời điểm, mức độ hiểu về đệ quy mà mỗi người sẽ có những nhận xét khác nhau. Tuy nhiên, theo mình nếu ai đã thuần thục dùng đệ quy thì sẽ có chung những nhận xét như sau.

– Về ưu điểm:

• Chương trình gắn gọn, dễ hiểu, giải quyết được nhiều vấn đề phức tạp.
• Một số vấn đề nếu không dùng đệ quy sẽ rất khó, cần nhiều thời gian suy nghĩ.

– Về khuyết điểm:

• Các hàm đệ quy được gọi lồng nhau dẫn đến việc khó debug, khi debug cần phải nắm rõ mình đang ở mức đệ quy nào.
• Tốc độ xử lí chậm cũng vì lì do liên tục gọi các hàm lồng nhau.
• Với input lớn, hàm đệ quy có thể dẫn đến việc bùng nổ trong việc gọi hàm, dẫn đến tình trạng tràn bộ nhớ stack (stack overflow).

– Do đó, ta cũng nên cân nhắc trong việc dùng đệ quy, tận dụng chứ không nên lạm dụng.

Qua hai bài viết chỉ mang tính chất giới thiệu về đệ quy, có lẽ các bạn chưa thể biết cách áp dụng đệ quy vào bài toán cụ thể. Theo như những ví dụ được trình bày phía trên, thì tất cả đều đã có sẵn công thức truy hồi nên việc viết chương trình là điều không khó. Trong khi đó, việc áp dụng đệ quy khó nhất là bước tìm ra công thức truy hồi hay đưa ra khái niệm tổng quát. Mình sẽ viết thêm một số bài trong đó sẽ hướng dẫn giải một số bài toán kinh điển để bạn có thể hình dung được hướng tiếp cận, cách tư duy kiểu đệ quy. Bạn có thể quay lại mục lục để tìm kiếm những bài viết hướng dẫn đó.

Chia sẻ:

• Tweet

Thích Đang tải...

Có liên quan