Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Ngô Quang Thạch

CẤU TRÚC DỮ LIỆU VÀ<br /> GIẢI THUẬT<br /> NGÔ QUANG THẠCH<br /> Email: thachnq@gmail.com<br /> ĐT: 01273984123<br /> <br /> Chương 2: Đệ qui và giải thuật đệ qui<br /> <br /> Khái niệm đệ qui<br /> <br /> Giải thuật đệ qui và chương trình đệ qui<br /> <br /> Các bài toán đệ qui căn bản<br /> <br /> Khái niệm đệ qui<br /> Ta nói một đối tượng là đệ quy nếu nó được định nghĩa<br /> qua chính nó hoặc một đối tượng khác cùng dạng với<br /> chính nó bằng quy nạp<br /> Ví dụ: Đặt hai chiếc gương cầu đối diện nhau.<br /> Trong chiếc gương 1 chứa hình chiếc gương 2. Chiếc gương 2<br /> lại chứa hình chiếc gương 1 nên tất nhiên nó chứa lại hình ảnh<br /> của chính nó trong chiếc gương 1… Ở một góc nhìn hợp lý, ta<br /> có thể thấy một dãy ảnh vô hạn của cả hai chiếc gương<br /> <br /> Ví dụ:<br /> Định nghĩa số tự nhiên<br /> 0 là số tự nhiên bé nhất.<br /> Nếu k là số tự nhiên thì k + 1 cũng là số tự nhiên<br /> Như vậy, số tự nhiên bắt đầu từ 0, ta có các số tự nhiên<br /> là: 0 + 1 = 1, 1 + 1 = 2,…<br /> Chuỗi ký tự<br /> Chuỗi rỗng là một chuỗi ký tự.<br /> Một chuỗi ký tự ghép với một ký tự bất kỳ là một chuỗi<br /> ký tự.<br /> <br /> Quá trình đệ qui<br /> Quá trình đệ qui gồm 2 phần:<br />  Trường hợp cơ sở (base case)<br />  Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sở<br /> Ví dụ:<br /> Hàm giai thừa: n!<br /> a) 0!=1<br /> b) Nếu n>0 thì n! = n*(n -1)!<br /> <br />