co ng .c om Phần 3: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT cu u du on g th an Chương 10: Giải thuật và thủ tục đệ quy Đại Học Bách Khoa Hà Nội Khoa Điện Tử - Viễn Thông Bộ môn Điện Tử - Tin Học Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 1 Nội dung Khái niệm th an Xây dựng thủ tục đệ quy co Cấu tạo giải thuật đệ quy Hoạt động của giải thuật đệ quy ng .c om Sự đệ quy Giải thuật đệ quy du on g Thủ tục đệ quy Phương pháp xây dựng cu u Cấu trúc thủ tục đệ quy Hoạt động của thủ tục đệ quy Nguyên tắc cài đặt Sự khử đệ quy Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 2 Nội dung .c co ng Tìm kiếm trong danh sách liên kết Bài toán Tháp Hà Nội Bài toán 8 con hậu om Các ví dụ minh họa th an Đánh giá thời gian thực hiện giải thuật cu u du on g Khái niệm Các ký hiệu Các quy tắc đánh giá Phân tích một số giải thuật Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin Học Chương 10: Giải Thuật Đệ Quy 3 Khái niệm đệ quy Các ví dụ: String ng .c Quy tắc 1: 1 char = String Quy tắc 2: String = 1 char + (sub) String om Khái niệm về đệ quy (recursion / recursive) N! N N if (x-1) th an Quy tắc 1: 1 Quy tắc 2: x co Số tự nhiên N du on g Quy tắc 1: 0! = 1 Quy tắc 2: n! = n (n-1)! Định nghĩa danh sách tuyến tính: cu u Quy tắc 1: L = rỗng là một DSTT Quy tắc 2: Nếu Ln-1 là một danh sách kích thước n-1 thì cấu trúc Ln=<a,Ln-1> cũng là một DSTT, với a là một phần tử có cùng kiểu dữ liệu như các phần tử trong Ln-1, và a đứng trước Ln-1 trong danh sách Ln Khoa Điện Tử Viễn Thông, Bộ Môn Điện Tử Tin H