Chương 2 Thuật toán đệ qui Bài giảng của PGS.TS. NGUYỄN ĐỨC NGHĨA Khoa học Máy tính Đại học Bách khoa Hà nội Nội dung 2.1. Khái niệm đệ qui 2.2. Thuật toán đệ qui 2.3. Một số ví dụ minh hoạ 2.4. Phân tích thuật toán đệ qui 2.5. Đệ qui có nhớ 2.6. Chứng minh tính đúng đắn của thuật toán đệ qui Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 3 2.1. Khái niệm đệ qui 2.1.1 Khái niệm đệ qui 2.1.2 Thuật toán đệ qui Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 4 Khái niệm đệ qui Trong thực tế ta thường gặp những đối tượng bao gồm chính nó hoặc được định nghĩa dưới dạng của chính nó. Ta nói các đối tượng đó được xác định một cách đệ qui. Ví dụ: Điểm quân số – Fractal – Các hàm được định nghĩa đệ qui – Tập hợp được định nghĩa đệ qui – Định nghĩa đệ qui của cây – ... Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 5 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 6 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 7 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 8 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 9 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 10 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 11 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 12 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 13 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 14 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 15 Đệ qui: Điểm quân Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 16 Fractals fractals là ví dụ về hình ảnh được xây dựng một cách đệ qui (đối tượng lặp lại một cách đệ qui). Cấu trúc dữ liệu và thuật toán - KHMT, ĐHBK Hà Nội 17 Hàm đệ qui (Recursive Functions) Các hàm đệ qui được xác định phụ thuộc vào biến nguyên không âm n theo sơ đồ sau: Bước cơ sở (Basic Step): Xác định giá trị của hàm