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.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 3: Đệ quy (Recursion) 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@gmail.com1 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical UniversityBài 3. Đệ quyNộ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 – Recursion2. Hanoi Tower (Web page)2 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University3.1. 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 University3.1. 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 University3.1. 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 University3.1. 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 Don Technical University3.1. Khái niệm về đệ quy (5/6) Có thể hình dung đệ quy qua 2 bước chính: quay xuôi (winding) và quay ngược (unwinding). Tại bước winding, lời giải bài toán gọi lại chính nó.  Với bước winding, lời gọi chính nó dừng khi thỏa mãn điều kiện dừng.  Điều kiện dừng thông thường được định nghĩa là tại bước đó đã đến bài toán cơ sở, có thể giải trực tiếp được.  Với mỗi hàm đệ quy cần có ít nhất một điều kiện dừng, nếu không sẽ lặp vô hạn.7 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University3.1. Khái niệm về đệ quy (6/6) Khi bước winding kết thúc, bước unwinding sẽ được thực hiện, các bài toán nhỏ trên được xem xét theo thứ tự ngược lại.  Bước này dừng lại khi quá trình đến bài toán gốc. Quá trình đệ quy kết thúc.8 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University3.2. Ví dụ về đệ quy (1/6) Ví dụ 1: Tính n!. F(n) = n* F(n-1) nếu n > 1 F(n) = 1 nếu n = 1 hoặc n = 0 Tính F(4) = ? Bước Winding Bước UnWinding F(4) = 4 * F(3) F(4) = 4 * 6 = 24 F(3) = 3 * F(2) F(3) = 3 * 2 = 6 F(2) = 2 * F(1) F(2) = 2 * 1 = 2 F(1) = 1 F(1) = 19 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University Ví dụ 1: Tính n! Ví dụ 1: Tính n! bằng đệ quy. long factorial(int n) #include { #include if((n==0)||(n==1)) return 1; long factorial(int); else return n*factorial(n-1); void main() } { int n; printf(Nhap vao mot so: ); scanf(%d,&n); printf(Gia tri cua giai thua: %ld,factorial(n)); getch(); }10 @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University 3.2. Ví dụ về đệ quy (2/6) Ví dụ 2: Tìm max của một dãy số. F(a,1) = a[1], F(a,2) = max(a[1],a[2]) F(a,n) = max(F(a,n-1),a[n]) if n > 2 Cho a[] = [3,2,5,7,1]. Tính F(a,5) = ? Bước Winding UnWinding Phase F(a,5) = max(F(a,4),a[5]) F(a,5) = max(7,1) = 7 F(a,4) = max(F(a,3),a[4]) F(a,4) = max(5,7) = 7 F(a,3) = max(F(a,2),a[3]) F(a,3) = max(3,5) = 5 F(a,2) = max(a[1],a[2]) F(a,2) = max(3,2)=311 @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University Ví dụ 2: Tìm max của một dãy số Ví dụ 2: Tìm max. int F(int *a, int n) #include { #include if (n==1) return a[0]; int F(int *, int); if (n==2) return max(a[0],a[1]); int max(int, int); if (n>2) return max(F ...