



















Preview text:
  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); }