1. Giới thiệu Bài toán Đệ quy
Đệ quy là một kỹ thuật lập trình khá hữu dụng trong nhiều trường hợp. Xét về bản chất, đệ quy chính là những vòng lặp nhưng dĩ nhiên đệ quy sẽ có những ưu điểm so với vòng lặp thông thường và khi sử dụng đệ quy sẽ đem lại kết quả tối ưu hơn với những cách thực hiện đơn giản hơn. Và tất nhiên những bài toán giải được bằng đệ quy thì có thể giải bằng vòng lặp thông thường (Quy trình khử đệ quy) (Có thể không tối ưu bằng).
Hình phía trên nhằm minh họa để ta dễ hiểu hơn về đệ quy. Hình được tạo ra khi tôi chạy chương trình team viewer trên 2 máy tính, trên máy tính này sẽ thấy màn hình máy tính kia và ngược lại… cứ như thế bên trong mỗi màn hình lại có chứa màn hình khác. Quá trình lặp đi lặp lại dường như đến vô tận (có thể xem quá trình này dừng lại khi kích thước khung hình được tạo ra quá nhỏ, không đủ pixel để hiển thị chi tiết)
Ví dụ thường thấy là khi ta để 2 tấm gương phản chiếu hướng vào nhau, nhìn trong tấm này sẽ thấy hình ảnh tấm kia, cứ như vậy số lượng hình ảnh sẽ tăng lên… đến vô tận.
2. Khái niệm Đệ quy
Đến đây chắc chúng ta đã phần nào hiểu rõ hơn về đệ quy. Yếu tố đầu tiên, đệ quy phải là một hàm (function), hàm này có khả năng tự gọi lại chính nó để sinh ra vòng lặp. Yếu tố thứ hai, căn cứ theo tính dừng của thuật toán thì đệ quy cũng phải có tính dừng; Nghĩa là sau một số vòng lặp hàm sẽ không gọi lại nó nữa – Kết thúc quá trình đệ quy.
Theo như 2 tính chất trên, khi định nghĩa hàm đệ quy chúng ta phải đảm bảo thực hiện 2 thành phần sau:
- Điểm dừng: Cần tạo ra một điều kiện dừng để xác định điểm kết thúc của vòng lặp. Việc thiết kế hàm đệ quy chính là quá trình đưa bài toán lớn dần trở thành bài toán nhỏ hơn, bài toán cứ vậy nhỏ dần đến mức mà nó đơn giản nhất có thể thì đưa ra lời giải và quay ngược trở lên, lấy lời giải tìm được để giải bài toán lớn hơn; Quá trình quay ngược kết thúc đồng nghĩa với việc bài toán lớn nhất được giải quyết. Điểm dừng ở đây chính là xác định bài toán con nhỏ nhất trong bài toán lớn ban đầu.
- Vòng lặp: Ngay trong bản thân hàm sẽ có phần để gọi lại chính nó, và ta thấy một điều hàm khi gọi lại sẽ có số lượng và kiểu đối số giống hàm ban đầu chỉ khác về giá trị. Khi xây dựng hàm đệ quy phải thật chính xác trong việc xác định vòng lặp và truyền giá trị cho đối số.
3. So sánh Đệ quy – Vòng lặp
Hình bên dưới đưa ra một số đặc điểm so sánh giữa Đệ quy và Vòng lặp để thấy ưu – nhược điểm của mỗi loại chương trình:
4. Phân loại đệ quy.
Xét theo cách lặp (cách thức tự gọi lại hàm) có thể chia đệ quy thành 4 dạng sau:
- Đệ quy tuyến tính
- Đệ quy nhị phân
- Đệ quy phi tuyến
- Đệ quy hỗ tương
4.1. Đệ quy tuyến tính: là dạng đệ quy thông thường như phần định nghĩa, trong thân hàm đệ quy sẽ được chia thành 2 phần: Điều kiện dừng và vòng lặp.
Ví dụ về đệ quy tuyến tính trong việc tính giai thừa
4.2.Đệ quy nhị phân: là dạng mở rộng của đệ quy tuyến tính. Nếu trong đệ quy tuyến tính chỉ gọi lại hàm 1 lần thì đệ quy nhị phân sẽ gọi lại 2 lần. Tùy theo yêu cầu bài toán có thể gọi lại nhiều lần hơn nữa, nhưng chung quy lại 1 dạng là đệ quy nhị phân
Với dạng đệ quy này tôi sử dụng bài toán fibonaci để minh họa, ta thấy thấy rằng khi tính phần tử thứ n(n>=2) thì cần có giá trị của 2 phần tử trước nó. Như vậy cần gọi lại hàm fibonaci 2 lần để có được giá trị của 2 phần tử đó.
4.3.Đệ quy phi tuyến:Với 2 dạng đệ quy trên ta có thể dung được luồng chạy của đệ quy, và thấy rằng mỗi lần thực hiện hàm thì số lần gọi lại đệ quy không đổi. Còn đối với loại đệ quy phi tuyến thì trong mỗi hàm số lần gọi lại sẽ khác nhau. Để tạo sự khác biệt này ta có thể dùng hàm xét điều kiện trước khi gọi lại hàm hoặc có thể kết hợp vòng lặp.
Ví dụ cho dạng đệ quy phi tuyến là một bài toán dãy số. Ta thấy rằng khi tính giá trị F(n) khi n càng lớn thì số lần gọi lại hàm F( ) càng nhiều, ở đây chúng ta sử dụng vòng lặp để quy định số lần gọi lại hàm F( )
4.4 Đệ quy tương hỗ: Với dạng đệ quy tương hỗ, việc gọi hàm không đơn thuần là tự gọi nó mà còn có gọi đến hàm khác, và hàm kia có khả năng gọi lại hàm ban đầu. Cứ như vậy tạo vòng lặp xen kẽ nhau, và tất nhiên dù là lặp dạng nào thì cũng cần có điểm dừng. Ở đây cần tạo điểm dừng trên cả 2 hàm, nếu 1 trong 2 hàm không có điểm dừng thì đệ quy sẽ vô tận.
Ví dụ minh họa
Trong bài viết Có một số Nội dung tham khảo từ Giáo trình của ĐH-CNTT
MicrosoftTech.Net
Lời bình mới nhất