tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 3: Đệ quy (Recursion)

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 3: Đệ quy (Recursion)" cung cấp những kiến thức về khái niệm về đệ quỵ; ví dụ về đệ quỵ; đệ quy đuôi; bài toán tháp Hanoi. Mời các bạn cùng tham khảo bài giảng để phục vụ cho học tập và nghiên cứu. | Cấu trúc dữ liệu và giải thuật Bài 3. Đệ quy Recursion Lecturer PhD. 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 3. Đệ quy Nội dung Khái niệm về đệ quy. Ví dụ về đệ quy. Đệ quy đuôi Tail Recursion Bài toán tháp Hanoi. Tham khảo 1. Kyle Loudon Mastering Algorithms with C Chapter 3 Recursion 2. Hanoi Tower Web page 2 @Copyright by PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm về đệ quy 1 6 Với phần lập trình viên để giải quyết bài toán lớn có thể sử dụng 1 quá trình dạng đệ quy. Ta nói m ột đối tượng là đệ qui nếu đối tượng này bao gồm chính nó như một bộ phận hoặc đối tượng được định nghĩa dưới dạng của chính nó. 3 @Copyright by PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm về đệ quy 2 6 Nguyên lý đệ quy cho phép hình thành bài toán từ chính nó. Trong tính toán để giải quyết vấn đề sử dụng hàm đệ quy hàm gọi chính nó với tham số thay đổi . Như vậy hàm đệ quy là hàm gọi lại chính nó. Với mỗi bước hàm thay đổi thông tin đầu vào và cho kết quả ngày càng gần với mục tiêu của bài toán. 4 @Copyright by PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm về đệ quy 3 6 Giả sử cần tính giai thừa của một số nguyên dương n. Giai thừa của n được viết n tích các phần tử từ n đến 1. Ví dụ 5 5 4 3 2 1 . Có thể thực hiện tính giai thừa bằng vòng lặp thông thường để tính tích. Một cách tiếp cận khác sử dụng đệ quy khi đó công thức tính giai thừa được viết dạng n n n - 1 n - 2 . . . 1 5 @Copyright by PhD. Ngo Huu Phuc Le Quy Don Technical University . Khái niệm về đệ quy 4 6 Có thể định nghĩa n theo cách khác là tích của n và giai thừa nhỏ hơn. Như vậy ta có n n n 1 . Ta x ử lý n - 1 giống như n với tham số nhỏ hơn. Ta có n - 1 n 1 n - 2 Tương tự n - 2 n 2 n - 3 quá trình trên kết thúc khi n 1. Với cách tiếp cận dạng đệ quy có thể định nghĩa lại cách tính giai thừa dạng n iif n 0 1 n n-1 6 @Copyright by PhD. Ngo Huu Phuc Le Quy .