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

Bài giảng "Cấu trúc dữ liệu và giải thuật: Đệ qui" trình bày các khái niệm đệ quy, ước số chung nhỏ nhất, tính giai thừa đệ qui, cây đệ qui chữ H, giải pháp đệ quy, chia để trị,... Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Đệ qui - TS. Đào Nam AnhDATA STRUCTURE AND ALGORITHMRecursionCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬTĐệ quiDr. Dao Nam AnhData Structure and Algorithm1Resource - ReferenceSlides adapted from Robert Sedgewick, and KevinWayne, edit by Dao Nam Anh.Major Reference:•Robert Sedgewick, and Kevin Wayne, “Algorithms”Princeton University, 2011, Addison Wesley•Algorithm in C (Parts 1-5 Bundle)- Third Edition byRobert Sedgewick, Addison-Wesley•Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.•Giải thuật và lập trình, Lê Minh Hoàng, Đại HọcSư Phạm, 2002Data Structure and Algorithm2Khái niệm•Là một phương pháp lập trình cho phép một hàm có thểgọi lại chính nó trực tiếp hoặc gián tiếp.Ví dụ: void Test(){Test();}Reproductive PartsM. C. Escher, 1948•Một chương trình đệ quy hoặc một định nghĩa đệ quy thìkhông thể gọi đến chính nó mãi mãi mà phải có mộtđiểm dừng đến một trường hợp đặc biệt nào đó, mà tagọi là trường hợp suy biến (degenerate case).Data Structure and Algorithm3Khái niệmPhương pháp thiết kế một giải thuật đệ quy:••Tham số hoá bài toán•Tìm trường hợp suy biếnPhân tích trường hợp chung : đưa bài toán dưới dạng bàitoán cùng loại nhưng có phạm vi giải quyết nhỏ hơntheo nghiã dần dần sẽ tiến đến trường hợp suy biếnData Structure and Algorithm4Khái niệmChương trình đệ quy gồm hai phần chính:1.2.Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm dừng)Phần đệ quy: Trong phần thân chương trình có lời gọiđến chính bản thân chương trình với giá trị mới củatham số nhỏ hơn giá trị ban đầuData Structure and Algorithm5