Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Đệ quy - Đào Nam Anh

Data Structure and Algorithm 1 DATA STRUCTURE AND ALGORITHM Recursion CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Đệ qui Dr. Dao Nam Anh Data Structure and Algorithm 2 Resource - Reference Slides adapted from Robert Sedgewick, and Kevin Wayne, edit by Dao Nam Anh. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley • Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường. • Giải thuật và lập trình, Lê Minh Hoàng, Đại Học Sư Phạm, 2002 Data Structure and Algorithm 3 Khái niệm • Là một phương pháp lập trình cho phép một hàm có thể gọi lại chính nó trực tiếp hoặc gián tiếp. Ví dụ: void Test() { Test(); } • Một chương trình đệ quy hoặc một định nghĩa đệ quy thì không thể gọi đến chính nó mãi mãi mà phải có một điểm dừng đến một trường hợp đặc biệt nào đó, mà ta gọi là trường hợp suy biến (degenerate case). Reproductive Parts M. C. Escher, 1948 Data Structure and Algorithm 4 Khái niệm Phương pháp thiết kế một giải thuật đệ quy: • Tham số hoá bài toán • Phân tích trường hợp chung : đưa bài toán dưới dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến trường hợp suy biến • Tìm trường hợp suy biến Data Structure and Algorithm 5 Khái niệm Chương trình đệ quy gồm hai phần chính: 1. Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm dừng) 2. Phần đệ quy: Trong phần thân chương trình có lời gọi đến chính bản thân chương trình với giá trị mới của tham số nhỏ hơn giá trị ban đầu Data Structure and Algorithm 6 Greatest Common Divisor Ước số chung nhỏ nhất • Gcd. Tìm số nguyên lớn nhất, chia hết bới hai số p và q. • Ví dụ. gcd(4032, 1272) = 24. 4032 = 26  32  71 1272 = 23  31  531 gcd = 23  31 = 24 Data Structure and Algorithm 7 Greatest Common Divisor Ước số chung nhỏ nhất • Gcd. Tìm số nguyên lớn nhất, chia hết bới hai số p và q. • Euclid's algorithm. [Euclid 300 BCE] gcd(4032, 1272)= gcd(1272, 216) = gcd(216, 192) = gcd(192, 24) = gcd(24, 0) = 24. gcd(p, q)  p if q  0 gcd(q, p % q) otherwise    base case reduction step, converges to base case 4032 = 3  1272 + 216 Data Structure and Algorithm 8 Greatest Common Divisor Ước số chung nhỏ nhất p p % qq x x x x x x x x p = 8x q = 3x gcd(p, q) = x q gcd gcd(p, q)  p if q  0 gcd(q, p % q) otherwise    base case reduction step, converges to base case Data Structure and Algorithm 9 Greatest Common Divisor Ước số chung nhỏ nhất base case reduction step public static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } gcd(p, q)  p if q  0 gcd(q, p % q) otherwise    base case reduction step, converges to base case Data Structure and Algorithm 10 Tính giai thừa đệ qui Data Structure and Algorithm 11 Recursive Graphics Đệ qui Đồ họa Data Structure and Algorithm 12 Data Structure and Algorithm 13 Data Structure and Algorithm 14 Htree – Cây đệ qui chữ H • H-tree bậc n.  Vẽ chữ H.  Vẽ đệ qui 4 H-trees bậc n-1, nối tại 4 chân. Và kích thước giảm nửa Bậc 1 size Bậc 2 Bậc 3 Data Structure and Algorithm 15 Htree – Cây đệ qui chữ H • H-tree bậc n.  Vẽ chữ H.  Vẽ đệ qui 4 H-trees bậc n-1, nối tại 4 chân. Và kích thước giảm nửa Bậc 1 size Bậc 2 Bậc 3 Data Structure and Algorithm 16 Htree – Cây đệ qui chữ H • H-tree bậc n.  Vẽ chữ H.  Vẽ đệ qui 4 H-trees bậc n-1, nối tại 4 chân. Và kích thước giảm nửa Bậc 1 tip size Bậc 2 Bậc 3 Data Structure and Algorithm 17 Htree in Java public class Htree { public static void draw(int n, double sz, double x, double y) { if (n == 0) return; double x0 = x - sz/2, x1 = x + sz/2; double y0 = y - sz/2, y1 = y + sz/2; StdDraw.line(x0, y, x1, y); StdDraw.line(x0, y0, x0, y1); StdDraw.line(x1, y0, x1, y1); draw(n-1, sz/2, x0, y0); draw(n-1, sz/2, x0, y1); draw(n-1, sz/2, x1, y0); draw(n-1, sz/2, x1, y1); } public static void main(String[] args) { int n = Integer.parseInt(args[0]); draw(n, .5, .5, .5); } } draw the H, centered on (x, y) recursively draw 4 half-size Hs Data Structure and Algorithm 18 Animated H-tree Data Structure and Algorithm 19 Animated H-tree Data Structure and Algorithm 20 Animated H-tree Data Structure and Algorithm 21 Animated H-tree Data Structure and Algorithm 22 Animated H-tree Data Structure and Algorithm 23 20% Animated H-tree Data Structure and Algorithm 24 20% 40% Animated H-tree Data Structure and Algorithm 25 20% 40% 60% 80% 100% Animated H-tree Data Structure and Algorithm 26 Data Structure and Algorithm 27 Tháp Hà nội Data Structure and Algorithm 28 Tháp Hà nội • Move all the discs from the leftmost peg to the rightmost one.  Only one disc may be moved at a time.  A disc can be placed either on empty peg or on top of a larger disc. start finish Edouard Lucas (1883) Data Structure and Algorithm 29 Tháp Hà nội: Giải pháp đệ qui Chuyển n-1 đĩa nhỏ sang phải. Chuyển n-1 đĩa nhỏ sang phải. Còn lại đĩa lớn nhất cyclic wrap-around Data Structure and Algorithm 30 Tháp Hà nội: Giải pháp đệ qui public class TowersOfHanoi { public static void moves(int n, boolean left) { if (n == 0) return; moves(n-1, !left); if (left) System.out.println(n + " left"); else System.out.println(n + " right"); moves(n-1, !left); } public static void main(String[] args) { int N = Integer.parseInt(args[0]); moves(N, true); } } moves(n, true) : move discs 1 to n one pole to the left moves(n, false): move discs 1 to n one pole to the right smallest disc Data Structure and Algorithm 31 Tháp Hà nội: Giải pháp đệ qui % java TowersOfHanoi 4 1 right 2 left 1 right 3 right 1 right 2 left 1 right 4 left 1 right 2 left 1 right 3 right 1 right 2 left 1 right % java TowersOfHanoi 3 1 left 2 right 1 left 3 left 1 left 2 right 1 left subdivisions of ruler every other move is smallest disc Data Structure and Algorithm 32 Tháp Hà nội: Giải pháp đệ qui 3, true n, left Data Structure and Algorithm 33 Tháp Hà nội: Giải pháp đệ qui 3, true 2, false 2, false 1 left 2 right 1 left 3 left 2 right 1 left1 left n, left 1 Data Structure and Algorithm 34 Tháp Hà nội: Giải pháp đệ qui 3, true 2, false 1, true 1, true 2, false 1 left 2 right 1 left 3 left 2 right 1 left1 left n, left 1 2 Data Structure and Algorithm 35 Tháp Hà nội: Giải pháp đệ qui 3, true 2, false 1, true 1, true 2, false 1 left 2 right 1 left 3 left 2 right 1 left1 left n, left 1 14 2 7 3 4 65 Data Structure and Algorithm 36 Tháp Hà nội: Giải pháp đệ qui 3, true 2, false 1, true 1, true 2, false 1, true 1, true 1 left 2 right 1 left 3 left 2 right 1 left1 left n, left 1 14 2 7 3 4 65 9 10 1211 17 18 2019 23 24 2625 138 16 21 2722 2815 Data Structure and Algorithm 37 Tháp Hà nội: Giải pháp đệ qui 3, true 2, false 1, true 1, true 2, false 1 left 2 right 1 left 3 left 2 right 1 left1 left n, left 1 14 2 7 3 4 65 9 10 1211 138 Data Structure and Algorithm 38 Tháp Hà nội: Giải pháp đệ qui 3, true 2, false 1, true 1, true 2, false 1, true 1, true 1 left 2 right 1 left 3 left 2 right 1 left1 left n, left 1 14 2 7 3 4 65 9 10 1211 17 18 2019 23 24 2625 138 16 21 2722 2815 Data Structure and Algorithm 39 Tháp Hà nội: Giải pháp đệ qui • Remarkable properties of recursive solution. Takes 2n - 1 moves to solve n disc problem.  Sequence of discs is same as subdivisions of ruler. Every other move involves smallest disc. • Recursive algorithm may reveal fate of world. Takes 585 billion years for n = 64 (at rate of 1 disc per second). Reassuring fact: any solution takes at least this long! Data Structure and Algorithm 40 Divide-and-Conquer Chia để trị • Chia để trị Chia thành nhiều vấn đề nhỏ hơn với cùng một cấu trúc. Giải quyết các vấn đề nhỏ bằng đệ qui cùng một giải pháp Nhóm các kết quả để có giải pháp cho cả bài toán • Ứng dụng thực tế.  Xử lý dữ liệu: FFT for signal processing.  Chương trình dịch: Parsers for programming languages.  Tính vi phân: Multigrid methods for solving PDEs.  Sắp xếp: Quicksort and mergesort for sorting.  Chía nhỏ vấn đề: Hilbert curve for domain decomposition. Divide et impera. Veni, vidi, vici. - Julius Caesar Data Structure and Algorithm 41 Fibonacci Numbers Dãy số Fibonacci Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ. Bài toán đặt ra như sau: • Các con thỏ không bao giờ chết • Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái) • Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới Data Structure and Algorithm 42 Fibonacci Numbers Dãy số Fibonacci • Giả sử từ đầu tháng 1 có một cặp mới ra đời thì đến giữa tháng thứ n sẽ có bao nhiêu cặp. • Ví dụ, n = 5, ta thấy:  Giữa tháng thứ 1: 1 cặp (ab) (cặp ban đầu)  Giữa tháng thứ 2: 1 cặp (ab) (cặp ban đầu vẫn chưa đẻ)  Giữa tháng thứ 3: 2 cặp (AB)(cd) (cặp ban đầu đẻ ra thêm 1 cặp con)  Giữa tháng thứ 4: 3 cặp (AB)(cd)(ef) (cặp ban đầu tiếp tục đẻ)  Giữa tháng thứ 5: 5 cặp (AB)(CD)(ef)(gh)(ik) (cả cặp (AB) và (CD) cùng đẻ) Data Structure and Algorithm 43 Fibonacci Numbers Dãy số Fibonacci • Bây giờ, ta xét tới việc tính số cặp thỏ ở tháng thứ n: F(n) • Nếu mỗi cặp thỏ ở tháng thứ n - 1 đều sinh ra một cặp thỏ con thì số cặp thỏ ở tháng thứ n sẽ là: F(n) = 2 * F(n - 1) Data Structure and Algorithm 44 Fibonacci Numbers and Nature pinecone cauliflower Data Structure and Algorithm 45 Fibonacci Numbers • Fibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, Fibonacci rabbits L. P. Fibonacci (1170 - 1250) F(n)  0 if n  0 1 if n 1 F(n1)  F(n2) otherwise      Data Structure and Algorithm 46 Fibonacci Numbers • Fibonacci numbers. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, public static long F(int n) { if (n == 0) return 0; if (n == 1) return 1; return F(n-1) + F(n-2); } F(n)  0 if n  0 1 if n 1 F(n1)  F(n2) otherwise      Data Structure and Algorithm 47 Đánh giá Đệ qui 1 • Q. Cách tính này có hiệu quả không F(50)? • A. Không hiệu quả. public static long F(int n) { if (n == 0) return 0; if (n == 1) return 1; return F(n-1) + F(n-2); } F(50) F(49) F(48) F(48) F(47) F(46) F(47) F(46) F(45) F(46) F(45) F(44) F(47) F(46) F(45) F(50) is called once. F(49) is called once. F(48) is called 2 times. F(47) is called 3 times. F(46) is called 5 times. F(45) is called 8 times. ... F(1) is called 12,586,269,025 times. recursion tree for naïve Fibonacci function F(50) Data Structure and Algorithm 48 Đánh giá đệ qui 2 • Q. Cách sau cho F(50) có hiệu quả không? • Hiệu quả public static long(int n) { long[] F = new long[n+1]; F[0] = 0; F[1] = 1; for (int i = 2; i <= n; i++) F[i] = F[i-1] + F[i-2]; return F[n]; } Data Structure and Algorithm 49 Summary – Kết luận Thông thường thay vì sử dụng lời giải đệ quy cho một bài toán, ta có thể thay thế bằng lời giải không đệ quy (khử đệ quy) bằng phương pháp lặp. Ưu điểm • Thuận lợi cho việc biểu diễn bài toán • Gọn (đối với chương trình) Hạn chế • Có khi không được tối ưu về thời gian • Có thể gây tốn bộ nhớ Chính vì vậy, trong lập trình người ta cố tránh sử dụng thủ tục đệ quy nếu thấy không cần thiết Data Structure and Algorithm 50 Discussion – Câu hỏi • https://sites.google.com/site/daonamanhedu/data- structure-algorithm