Mời các bạn cùng tham khảo bài giảng "Cấu trúc dữ liệu và giải thuật – Bài 12: Khử đệ quy" để nắm chi tiết nội dung những kiến thức khái niệm chung, khử đệ quy cho bài toán tính giai thừa, khử đệ quy cho bài toán Fibonacci, khử đệ quy cho bài toán tháp Hanoi, khử đệ quy cho bài toán QuickSort. | Cấu trúc dữ liệu và giải thuật Bài 12. Khử đệ quy Giảng viên TS. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University Bài 12. Khử đệ quy Nội dung bài học . Khái niệm chung . Khử đệ quy cho bài toán tính giai thừa. . Khử đệ quy cho bài toán Fibonacci. . Khử đệ quy cho bài toán tháp Hanoi. . Khử đệ quy cho bài toán QuickSort. Tham khảo 1. Data structures and Algorithms 2. Kyle Loudon Mastering Algorithms Chapter 6 Stacks and Queues 3. Elliz Horowitz Fundamentals of Data Structures Chapter 3 Stacks and Queues 4. Deshpande Kakle C and Data Structures Chapter 19. Stacks and Queues. 5. Bài giảng TS Nguyễn Nam Hồng. 2 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University . Khái niệm chung 1 7 Đối với hệ điều hành thông thường khi một chương trình con được gọi nó sẽ thực hiện 1. Trước hết hệ điều hành lưu tất cả các thông tin cần thiết của chương trình con thông tin cần thiết . 2. Tiếp theo chuẩn bị gọi chương trình và chuyển quyền điều khiển cho chương trình con. 3. Sau đó khi kết thúc chương trình con hệ điều hành lấy lại các thông tin đã lưu ở bước 1 và chuyển quyền điều khiển đến nơi gọi chương trình con. Lưu ý các thông tin được lưu tại Stack của chương trình. 3 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University . Khái niệm chung 2 7 Stack chương trình Đối với các ngôn ngữ bậc cao sẽ sử dụng Stack chương trình cho mỗi lời gọi chương trình con. Như vậy khi chương trình con được gọi mọi thông tin của môi trường tại nơi gọi chương trình con sẽ được đưa vào stack chương trình. Khi quay trở lại nơi gọi chương trình con các thông tin được lấy lại từ stack chương trình. Với cách này bộ nhớ cần thiết sẽ rất lớn khi áp dụng cho bài toán đệ quy. 4 @copyright by PhD Ngo Huu Phuc Le Quy Don Technical University . Khái niệm chung 3 7 Sử dụng bản ghi dạng stack riêng Một phương pháp đơn giản để có thể kiểm soát được bộ nhớ của .
