Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Đệ quy (Recursion) - Ngô Hữu Phước

Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: [email protected] Cấu trúc dữ liệu và giải thuật Bài 3. Đệ quy (Recursion) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University1 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) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University2 3.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ó. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University3 3.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. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University4 3.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) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University5 3.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)!) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University6 3.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. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University7 3.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. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University8 3.2. Ví dụ về đệ quy (1/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University9 Bước Winding F(4) = 4 * F(3) F(3) = 3 * F(2) F(2) = 2 * F(1) F(1) = 1 Bước UnWinding F(4) = 4 * 6 = 24 F(3) = 3 * 2 = 6 F(2) = 2 * 1 = 2 F(1) = 1 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) = ? Ví dụ 1: Tính n! Ví dụ 1: Tính n! bằng đệ quy. #include #include long factorial(int); void main() { int n; printf("Nhap vao mot so: "); scanf("%d",&n); printf("Gia tri cua giai thua: %ld",factorial(n)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University10 long factorial(int n) { if((n==0)||(n==1)) return 1; else return n*factorial(n-1); } 3.2. Ví dụ về đệ quy (2/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University11 Bước Winding F(a,5) = max(F(a,4),a[5]) F(a,4) = max(F(a,3),a[4]) F(a,3) = max(F(a,2),a[3]) F(a,2) = max(a[1],a[2]) UnWinding Phase F(a,5) = max(7,1) = 7 F(a,4) = max(5,7) = 7 F(a,3) = max(3,5) = 5 F(a,2) = max(3,2)=3 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) = ? Ví dụ 2: Tìm max của một dãy số Ví dụ 2: Tìm max. #include #include int F(int *, int); int max(int, int); void main() { int n; int a[100]; printf("Nhap vao so phan tu: "); scanf("%d",&n); for(int i=0;i<n;i++) { printf("Nhap phan tu a[%d]=",i); scanf("%d",&a[i]); } printf("Gia tri max: %d",F(a,n)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University12 int F(int *a, int n) { if (n==1) return a[0]; if (n==2) return max(a[0],a[1]); if (n>2) return max(F(a,n-1),a[n-1]); } int max(int a, int b) { if(a>b) return a; else return b; } 3.2. Ví dụ về đệ quy (3/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University13 Bước Winding F(a,4) = F(a,3) + a[4] F(a,3) = F(a,2) + a[3] F(a,2) = F(a,1) + a[2] F(a,1) = a[1] Bước UnWinding F(a,4) = 11 + 5 = 16 F(a,3) = 8 + 3 = 11 F(a,2) = 1 + 7 = 8 F(a,1) = 1 Ví dụ 3: Tính tổng của một dãy số. F(a,1) = a[1] F(a,n) = F(a,n-1)+a[n] if n > 1 Cho a[] = [1,7,3,5], Tính F(a,4) = ? Ví dụ 3: Tính tổng của một dãy số Ví dụ 3: Tính tổng một dãy số. #include #include long sum(int*, int); void main() { int n; int a[100]; printf("Nhap vao so pt: "); scanf("%d",&n); for(int i=0;i<n;i++) { printf("Nhap pt a[%d]=",i); scanf("%d",&a[i]); } printf("Tong cua cac pt: %ld",sum(a,n)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University14 long sum(int * a, int n) { if(n==1) return a[0]; else return sum(a,n-1)+a[n-1]; } 3.2. Ví dụ về đệ quy (4/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University15 Bước Winding F(4) = F(3) + F(2) F(3) = F(2) + F(1) F(2) = 1 F(1) = 1 Bước UnWinding F(4) = 2 + 1 = 3 F(3) = 1 + 1 = 2 F(2) = 1 F(1) = 1 Ví dụ 4: Dãy số Fibonacci. F(n) = 1 nếu n = 1 hoặc n = 2 F(n) = F(n-1) + F(n-2) nếu n > 2 Tính F(4) = ? Ví dụ 4: Tính số Fibonacci Ví dụ 4: Tính số fibonacci. #include #include long fibonacci( int); void main() { int n; printf("Nhap vao n: "); scanf("%d",&n); printf("Fibonacci cua %d: %ld",n,fibonacci(n)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University16 long fibonacci(int n) { if((n==1) || (n==2)) return 1; else return fibonacci(n-1)+fibonacci(n-2); } 3.2. Ví dụ về đệ quy (5/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University17 Bước Winding F(2,1) = F(F(1,1),0) F(1,1) = F(F(0,1),0) F(0,1) = F(1,0) F(1,0) = 2 Bước UnWinding F(2,1) = F(3,0) = 4 F(1,1) = F(2,0) = 3 F(0,1) = 2 F(1,0) = 2 Ví dụ 5: Hàm Ackermann. F(m,0) = m + 1 nếu m >= 0 F(0,n) = F(1,n-1) nếu n > 0 F(m,n) = F(F(m-1,n),n-1) nếu m >= 1 và n > 0 Tính F(2,1) = ? Ví dụ 5: Hàm Ackermann Ví dụ 5: Hàm Ackermann #include #include int Ackermann(int, int); void main() { int m, n; printf("Nhap vao m= "); scanf("%d",&m); printf("Nhap vao n= "); scanf("%d",&n); printf("Ackermann cua %d va %d: %d",m,n,Ackermann(m,n)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University18 int Ackermann(int m, int n) { if((m>=0) && (n==0)) return m+1; if((n>0) && (m==0)) return Ackermann(1,n-1); if((m>=1) && (n>0)) return Ackermann(Ackermann(m-1,n), n-1); } 3.2. Ví dụ về đệ quy (6/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University19 Ví dụ 6: Pascal Identifier Definition Character Character Digit Identifiers: Name of Constants, Variables, Functions, Procedure, Programs, Labels, 3.3. Đệ quy đuôi - Tail Recursion (1/6)  Hàm đệ quy được gọi là đệ quy đuôi - tail recursive – nếu các lời gọi đệ quy trong hàm là công việc cuối cùng của quá trình đệ quy.  Trong quá trình đệ quy, các trạng thái của quá trình trước được lưu cho quá trình sau. Tuy vậy, với đệ quy đuôi, việc lưu trên là không cần thiết.  Hàm đệ quy đuôi không có bước quay ngược.  Tính chất trên không quá quan trọng vì phần lớn các bộ xử lý hiện nay thực hiện được điều này tự động. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University20 3.3. Đệ quy đuôi (2/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University21 Bước Winding F(4,1) = F(3,4) F(3,4) = F(2,12) F(2,12) = F(1,24) F(1,24) = 24 Ví dụ 1: Tính n! F(n, a) = F(n-1, n*a) nếu n>1 F(n,a) = a nếu n = 1 hoặc n = 0 Tính F(4,1) = ? Bước UnWinding Không thực hiện gì Ví dụ 1: Tính n! bằng đệ quy đuôi Ví dụ 1: Tính n! bằng đệ quy đuôi. #include #include long factorial_tail(int, int); void main() { int n; printf("Nhap vao mot so: "); scanf("%d",&n); printf("Gia tri cua giai thua: %ld",factorial_tail(n,1)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University22 long factorial_tail(int n, int a) { if (n>1) return factorial_tail(n-1,n*a); else return a; } 3.3. Đệ quy đuôi (3/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University23 Bước Winding F(a,5,a[n-1]) = F(a,4,7) F(a,4,7) = F(a,3,7) F(a,3,7) =F(a,2,9) F(a,2,9) = F(a,1,9) F(a,1,9) = 9 Ví dụ 2: Tìm phần tử Maximum trong chuỗi số. F(a,1,b) = b, F(a,n,b) = F(a,n-1,max(b,a[n-1]) nếu n > 1 Cho mảng a[5] = [3,9,5,7,1]. Tính F(a,5,a[5]) = ? Bước UnWinding Không thực hiện gì Ví dụ 2: Tìm max bằng đệ quy đuôi Ví dụ 2: Tìm max bằng đệ quy đuôi. #include #include int F_tail(int *, int, int); int max(int, int); void main() { int n; int a[100]; printf("Nhap vao so phan tu: "); scanf("%d",&n); for(int i=0;i<n;i++) { printf("Nhap phan tu a[%d]=",i); scanf("%d",&a[i]); } printf("Gia tri max: %d",F_tail(a,n,a[n-1])); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University24 int F_tail(int *a, int n, int b) { if (n==1) return b; else return F_tail(a,n-1,max(b,a[n-2])); } int max(int a, int b) { if(a>b) return a; else return b; } 3.3. Đệ quy đuôi (4/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University25 Bước Winding F(a,4,5) = F(a,3,8) F(a,3,8) = F(a,2,15) F(a,2,15) = F(a,1,16) F(a,1,16) = 16 Ví dụ 3: Tính tổng của chuỗi số. F(a,1,b) = b F(a,n,b) = F(a,n-1,b+a[n-1]) nếu n > 1 Cho a[4] = [1,7,3,5]. Tính F(a,4,a[4]) = ? Bước UnWinding Không thực hiện gì Ví dụ 3: Tính tổng bằng đệ quy đuôi Ví dụ 3: Tính tổng bằng đệ quy đuôi #include #include long sum_tail(int*, int, long); void main() { int n; int a[100]; printf("Nhap vao so pt: "); scanf("%d",&n); for(int i=0;i<n;i++) { printf("Nhap pt a[%d]=",i); scanf("%d",&a[i]); } printf("Tong cua cac pt: %ld",sum_tail(a,n-1,a[n-1])); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University26 long sum_tail(int * a, int n, long b) { if(n==0)return b; else return sum_tail(a,n-1,b+a[n-1]); } 3.3. Đệ quy đuôi (5/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University27 Bước Winding F(4,0,1) = F(3,1,1) F(3,1,1) = F(2,1,2) F(2,1,2) = F(1,2,3) F(1,2,3) = 3 Ví dụ 4: Số Fibonacci. F(n,a,b) = b nếu n = 1 hoặc n = 2 F(n,a,b) = F(n-1,b,a+b) nếu n > 2 Tính F(4,0,1) = ? Bước UnWinding Không thực hiện gì Ví dụ 4: Tính Fibonacci bằng đệ quy đuôi Ví dụ 4: Tính Fibonacci bằng đệ quy đuôi. #include #include long fibonacci(int, int, int); void main() { int n; printf("Nhap vao n: "); scanf("%d",&n); printf("Fibonacci cua %d: %ld",n,fibonacci(n,0,1)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University28 long fibonacci(int n, int a, int b) { if (n==1) return b; else return fibonacci(n-1,b,a+b); } 3.3. Đệ quy đuôi (6/6) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University29 Bước Winding F(54,21) = F(21,12) F(21,12) = F(12,9) F(12,9) = F(9,3) F(9,3) = 3 Ví dụ 5: Euler GCD (greatest common divisor) Algorithm (n > m) F(n,m) = m nếu n div m = 0 F(n, m) = F(m, n mod m) nếu n mod m 0 Tính F(54,21) = ? Bước UnWinding Không thực hiện gì Ví dụ 5: Tính ước số chung lớn nhất Ví dụ 5: Hàm Euler GCD #include #include int Ackermann(int, int); void main() { int m, n; printf("Nhap vao m= "); scanf("%d",&m); printf("Nhap vao n= "); scanf("%d",&n); printf("Ackermann cua %d va %d: %d",m,n,Ackermann(m,n)); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University30 int Ackermann(int m, int n) { if((m>=0) && (n==0)) return m+1; if((n>0) && (m==0)) return Ackermann(1,n-1); if((m>=1) && (n>0)) return Ackermann(Ackermann(m-1,n), n-1); } 3.4. Tháp Hà nội (1/8)  Bài toán được nhà toán học người Pháp Edouard Lucas đưa ra vào năm 1883.  Bài toán Tháp Hà nội được giới thiệu trong nhiều tài liệu về thuật toán. Bên cạnh đó, rất nhiều web sites cũng đề cập tới bài toán này. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University31 3.4. Tháp Hà nội (2/8) Bài toán  Có n chiếc đĩa có kích thước khác nhau và có 3 stacks có tên A, B, C.  Ban đầu, n đĩa được đặt tại stack A, sao cho không có đĩa lớn nằm trên đĩa nhỏ.  Nhiệm vụ đặt ra là chuyển tất cả các đĩa ở stack A sang stack C. Sử dụng stack B làm trung gian trong quá trình chuyển.  Mỗi lần chuyển 1 đĩa và không có đĩa lớn nằm trên đĩa nhỏ. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University32 3.4. Tháp Hà nội (3/8) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University33 3.4. Tháp Hà nội (4/8)  Để giải quyết bài toán trên, số bước chuyển đĩa ít nhất là bao nhiêu?  Để trả lời câu hỏi trên, cần đưa ra cách đệ quy tối ưu và phân tích chúng.  Có thể phân tích được không trong trường hợp tổng quát hóa, không chỉ xét 3 đĩa? @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University34 3.4. Tháp Hà nội (5/8) Giải pháp đệ quy:  Ban đầu, đĩa lớn nhất được đặt tại đáy của stack A.  Giả sử rằng nó được chuyển sang stack C (cách tốt nhất để tiếp cận bài toán), như vậy n-1 đĩa nhỏ hơn phải được chuyển sang stack B.  Như vậy, cần chuyển n-1 đĩa nhỏ từ A sang B, sử dụng C làm stack trung gian.  Sau khi thực hiện được việc trên, cần chuyển n-1 đĩa còn lại từ B sang C, sử dụng stack A làm stack trung gian. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University35 3.4. Tháp Hà nội (6/8)  Ký hiệu: "A ==> B" có nghĩa chuyển 1 đĩa trên đỉnh của A sang B.  Giải thuật: Function HanoiTower (n, A,B,C) 1. if n < 0 then return 2. HanoiTower (n-1, A,C,B) 3. A ==> B 4. HanoiTower (n-1, C,B,A) End Function @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University36 3.4. Tháp Hà nội (7/8) @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University37 Phân tích bài toán với n = 2 Tháp Hà nội #include "stdio.h" #include "conio.h" void HanoiTower(int, char, char, char); void main() { int m; printf("Nhap vao so dia m = "); scanf("%d",&m); printf("Ket qua cac buoc \n"); HanoiTower(m,'A','C','B'); getch(); } @Copyright Dr. Ngo Huu Phuc, Le Quy Don Technical University38 void HanoiTower(int m, char a, char b, char c) { if(m>0) { HanoiTower(m-1,a,c,b); printf("Chuyen dia %d tu %c sang %c\n",m,a,b); HanoiTower(m-1,c,b,a); } } 3.4. Tháp Hà nội (8/8) Thời gian và giới hạn:  Gọi T(n) là số phép chuyển đĩa trong giải thuật để chuyển n đĩa.  Từ giải thuật, có thể thấy: T(n) = 0 nếu n < 0 T(n) = 2T(n-1) + 1 nếu n > 0  Giải bài toán trên, ta có: T(n) = 2n - 1 với mọi n > 0.  Như vậy, T(n) là hữu hạn, và giải thuật sẽ dừng. @Copyright by PhD. Ngo Huu Phuc, Le Quy Don Technical University39/39