Chương 2: Đệ qui và Ví dụ | Môn Cấu trúc dữ liệu và thuật toán - Trường Đại học Khoa học, Đại học Huế

lOMoAR cPSD| 58702377
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Cấu trúc dữ liệu và thuật toán Nguyễn Khánh Phương Computer Science department
School of Information and Communication technology
E-mail: phuongnk@soict.hust.edu.vn Nội dung khóa học lOMoAR cPSD| 58702377
Chương 1. Các khái niệm cơ bản Chương 2. Các sơ ồ thuật toán
Chương 3. Các cấu trúc dữ liệu cơ bản Chương 4. Cây Chương 5. Sắp xếp Chương 6. Tìm kiếm Chương 7. Đồ thị 2 lOMoAR cPSD| 58702377
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Chương 2. Các sơ ồ thuật toán Nguyễn Khánh Phương Computer Science department
School of Information and Communication technology
E-mail: phuongnk@soict.hust.edu.vn lOMoAR cPSD| 58702377 N i dung 1. Khái niệm ệ qui 2. Thuật toán ệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán ệ qui 5. Đệ qui có nhớ 6. Thuật toán quay lui 4 lOMoAR cPSD| 58702377 N i dung 1. Khái niệm ệ qui 2. Thuật toán ệ qui
3. Một số ví dụ minh hoạ
4. Phân tích thuật toán ệ qui 5. Đệ qui có nhớ 6. Thuật toán quay lui 5 lOMoAR cPSD| 58702377 1. 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 – ... lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377
Ví dụ Đệ qui: Điểm quân lOMoAR cPSD| 58702377 Ví dụ Đệ qui: 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). 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 tại n=0: f(0). lOMoAR cPSD| 58702377
Bước ệ qui (Recursive Step): Cho giá trị của f(k), k ≤ n, ưa ra qui tắc tính giá trị của f(n+1). Ví dụ 1: f(0) = 3, n = 0 f(n+1) = 2f(n) + 3, n > 0
Khi ó ta có: f(1) = 2 × 3 + 3 = 9, f(2) = 2 × 9 + 3 = 21, ...
Hàm ệ qui (Recursive Functions)
Ví dụ 2: Định nghĩa ệ qui của n! f(0) = 1 f(n) = n * f(n-1)
Để tính giá trị của hàm ệ qui ta thay thế dần theo ịnh nghĩa ệ qui ể thu ược biểu thức
với ối số càng ngày càng nhỏ cho ến tận iều kiện ầu. Chẳng hạn: lOMoAR cPSD| 58702377
5! = 5 · 4! = 5 · 4 · 3! = 5 · 4 · 3 · 2! = 5 · 4 · 3 · 2 · 1!
= 5 · 4 · 3 · 2 · 1 · 0! = 5 · 4 · 3 · 2 · 1 · 1 = 120 int factorial(int n){ if (n==0) return 1;
else return n*factorial(n-1); } factorial(4); factorial(4) int factorial(int n){ if (n==0) return 1;
else return n*factorial(n-1); }