Bài giảng Cấu trúc dữ liệu và giải thuật: Đệ qui - TS. Đào Nam Anh

DATA STRUCTURE AND ALGORITHM<br /> Recursion<br /> CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT<br /> Đệ qui<br /> Dr. Dao Nam Anh<br /> <br /> Data Structure and Algorithm<br /> <br /> 1<br /> <br /> Resource - Reference<br /> Slides adapted from Robert Sedgewick, and Kevin<br /> Wayne, edit by Dao Nam Anh.<br /> Major Reference:<br /> <br /> •<br /> <br /> Robert Sedgewick, and Kevin Wayne, “Algorithms”<br /> Princeton University, 2011, Addison Wesley<br /> <br /> •<br /> <br /> Algorithm in C (Parts 1-5 Bundle)- Third Edition by<br /> Robert Sedgewick, Addison-Wesley<br /> <br /> •<br /> <br /> Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.<br /> <br /> •<br /> <br /> Giải thuật và lập trình, Lê Minh Hoàng, Đại Học<br /> Sư Phạm, 2002<br /> Data Structure and Algorithm<br /> <br /> 2<br /> <br /> Khái niệm<br /> <br /> •<br /> <br /> Là một phương pháp lập trình cho phép một hàm có thể<br /> gọi lại chính nó trực tiếp hoặc gián tiếp.<br /> Ví dụ: void Test()<br /> {<br /> Test();<br /> }<br /> Reproductive Parts<br /> M. C. Escher, 1948<br /> <br /> •<br /> <br /> Một chương trình đệ quy hoặc một định nghĩa đệ quy thì<br /> không thể gọi đến chính nó mãi mãi mà phải có một<br /> điểm dừng đến một trường hợp đặc biệt nào đó, mà ta<br /> gọi là trường hợp suy biến (degenerate case).<br /> Data Structure and Algorithm<br /> <br /> 3<br /> <br /> Khái niệm<br /> Phương pháp thiết kế một giải thuật đệ quy:<br /> <br /> •<br /> •<br /> <br /> Tham số hoá bài toán<br /> <br /> •<br /> <br /> Tìm trường hợp suy biến<br /> <br /> Phân tích trường hợp chung : đưa bài toán dưới dạng bài<br /> toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn<br /> theo nghiã dần dần sẽ tiến đến trường hợp suy biến<br /> <br /> Data Structure and Algorithm<br /> <br /> 4<br /> <br /> Khái niệm<br /> Chương trình đệ quy gồm hai phần chính:<br /> <br /> 1.<br /> 2.<br /> <br /> Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm dừng)<br /> Phần đệ quy: Trong phần thân chương trình có lời gọi<br /> đến chính bản thân chương trình với giá trị mới của<br /> tham số nhỏ hơn giá trị ban đầu<br /> <br /> Data Structure and Algorithm<br /> <br /> 5<br /> <br />