Bài giảng Recursion

University of FloridaDept. of Computer & Information Science & EngineeringCOT 3100Applications of Discrete StructuresDr. Michael P. Frank Slides for a Course Based on the TextDiscrete Mathematics & Its Applications (5th Edition)by Kenneth H. Rosen Module #16:Đệ quiRecursion Rosen 5th ed., §§3.4-3.5 ~34 slides, ~2 lectures Định nghĩa đệ qui§3.4: Recursive Definitions Trong qui nạp, ta chứng minh mọi phần tử của tập vô hạn thoả mãn mệnh đề P nào đó bằng cách: Chứng minh tính đúng đắn của mệnh đề cho các phần tử lớn hơn mà biểu diễn qua các phần tử bé hơn. Trong định nghĩa đệ qui, tương tự ta định nghĩa hàm số, mệnh đề, tập hợp, hay một cấu trúc phức tạp hơn trên miền biến thiên vô hạn bằng cách: định nghĩa hàm, giá trị mệnh đề, tính chất thuộc của tập hợp, hoặc cấu trúc của các phần tử lớn hơn biểu diễn qua các phần tử nhỏ hơn. Trong qui nạp cấu trúc, ta chứng minh qui nạp các tính chất của các đối tượng xác định đệ qui theo cách mà nó song hành xây dựng lên chính đối tượng đệ qui đó. Đệ qui - Recursion Đệ qui là thuật ngữ nói chung trong thực hành để định nghĩa một đối tượng thông qua chính nó Hoặc một phần của chính nó Điều đó trông có vẻ luẩn quẩn, nhưng không hẳn như vậy. Chứng minh qui nạp thiết lập tính đúng đắn của P(n+1) đệ qui qua thuật ngữ của P(n). Có các thuật toán, định nghĩa hàm, dãy, tập hợp và các cấu trúc khác đệ qui. Các hàm định nghĩa đệ quiRecursively Defined Functions T/h đơn giản nhất: Một cách đ/n hàm f:NS (với tập S bất kỳ) hoặc dãy an=f(n) như sau: Định nghĩa f(0). Với n>0, định nghĩa f(n) thông qua f(0),…,f(n−1). VD: Định nghĩa dãy an :≡ 2n đệ qui: G/s a0 :≡ 1. Với n>0, đặt an :≡ 2an-1. Ví dụ khác - Another Example G/s ta định nghĩa f(n) đối với mọi nN đệ qui như sau: G/s f(0)=3 Với mọi nN, cho f(n+1)=2f(n)+3 Các giá trị sau đây bằng bao nhiêu? f(1)= f(2)= f(3)= f(4)= 9 21 45 93 Định nghĩa giai thừa đệ qui Recursive definition of Factorial Cho định nghĩa qui nạp (đệ qui) của hàm giai thừa như sau, F(n) :≡ n! :≡ ∏1≤i≤n i = 12…n. T/h cơ sở: F(0) :≡ 1 Phần đệ qui: F(n) :≡ n  F(n−1). F(1)=1 F(2)=2 F(3)=6 Một sô ví dụ đơn giản Viết định nghĩa đệ qui cho: i+n (i nguyên, n tự nhiên) chỉ sử dụng s(i) = i+1. a·n (a thực, n tự nhiên) chỉ sử dụng cộng an (a thực, n tự nhiên) chỉ sử dụng nhân ∑0≤i≤n ai (cho dãy sô bất kỳ {ai}) ∏0≤i≤n ai (cho dãy số bất kỳ {ai}) ∩0≤i≤n Si (cho dãy tập hợp bất kỳ {Si}) Dãy FibonacciThe Fibonacci Series Dãy Fibonacci fn≥0 là dãy nổi tiếng được định nghĩa như sau: f0 :≡ 0, f1 :≡ 1, fn≥2 :≡ fn−1 + fn−2 Leonardo Fibonacci1170-1250 0 1 1 2 3 5 8 13 C/m qui nạp về dãy Fibonacci Định lý: fn αn−2, trong đó α = (1+51/2)/2 ≈ 1.61803. C/m. (Sử dụng qui nạp mạnh.) G/s P(n) = (fn > αn−2). T/h cơ sở: với n=3, nhận thấy α αk−3 và fk > αk−2. Vậy, fk+1 = fk + fk−1 > αk−2 + αk−3 = αk−1. Suy ra P(k+1). ■ Lamé’s Theorem Định lý: a,bN, a≥b>0,số bước của thuật toán Euclidtìm ước số chung lớn nhất gcd(a,b) ≤ 5k, trong đó k = log10 b+1 là số các chữ số thập phân của b. Như vậy thuật toán Euclid là tuyến tính với số các chữ số của b. Chứng minh: Sử dụng dãy Fibinacci! Xem 2 trang tiếp theo. Gabriel Lamé1795-1870 Proof of Lamé’s Theorem Xét dãy các phép chia sử dụng trong thuật toán Euclid: r0 = r1q1 + r2 with 0 ≤ r2 r2 > … > rn, mỗi thương qi ≡ ri−1/ri ≥ 1. Vì rn−1 = rnqn và rn−1 > rn, qn ≥ 2. Nên ta có các quan hệ sau giữa r và f: rn ≥ 1 = f2 rn−1 ≥ 2rn ≥ 2f2 = f3 rn−2 ≥ rn−1 + rn ≥ f2 + f3 = f4 … r2 ≥ r3 + r4 ≥ fn−1 + fn−2 = fn b = r1 ≥ r2 + r3 ≥ fn + fn−1 = fn+1. Vậy, nếu n>2 phép chia được sử dụng, thì b ≥ fn+1 > αn−1. Do đó, log10 b > log10(αn−1) = (n−1)log10 α ≈ (n−1)0.208 > (n−1)/5. Nếu b có k chữ số thập phân, thì log10 b b N) {Returns bn mod m.}if n=0 then return 1 elsereturn (b·mpower(b,n−1,m)) mod m Nhận thấy thuật toán dùng Θ(n) bước! Thuật toán lũy thừa #2 Sử dụng công thức b2k = bk·2 = (bk)2. procedure mpower(b,n,m) {same signature} if n=0 then return 1else if 2|n then return mpower(b,n/2,m)2 mod melse return (mpower(b,n−1,m)·b) mod m Độ phức tạp thời gian là bao nhiêu? Θ(log n) steps Phương án khác một chút A Slight Variation Gần giống nhưng dùng Θ(n) thời gian! procedure mpower(b,n,m) {same signature} if n=0 then return 1else if 2|n then return (mpower(b,n/2,m)· mpower(b,n/2,m)) mod melse return (mpower(b,n−1,m)·b) mod m The number of recursive calls made is critical! ầ Thuật toán Euclide đệ quiRecursive Euclid’s Algorithm procedure gcd(a,bN)if a = 0 then return belse return gcd(b mod a, a) Nhận thấy thuật toán đệ qui thường đơn giản hưn thuật toán lặp… Tuy nhiên, chúng thường dùng nhiều ngăn xếp hơn, nếu chương trình dịch của chúng ta không đủ thông minh. Tìm kiếm tuyến tính đệ quiRecursive Linear Search Nhận thấy không có cải tiến thực sự khi sử dụng đệ qui ở đây so với vòng lặp for loc := i to j… procedure search(a: series; i, j: integer; x: item to be found) {Find x in series a at a location ≥i and 1, theo giả thiết qui nạp mạnh, fibonacci(n−1) và fibonacci(n−2) thực hiện fn−1 và fn−1−1 phép cộng tương ứng, và fibonacci(n) cộng thêm 1 nữa, tổng cộng là fn−1+ fn−1−1+1 = fn+fn−1+1 = fn+1+1. ■ Thuật toán hiệu quả hơnA more efficient algorithm procedure findFib(a,b,m,n){Given a=fm−1, b=fm, and m≤n, return fn}if m=n return breturn findFib(b, a+b, m+1, n) procedure fastFib(n) {Find fn in Θ(n) steps.}if n=0 return 0return findFib(0,1,1,n) Sắp xếp trộn Sắp xếp trộn đệ quiRecursive Merge Sort procedure sort(L = 1,…, n)if n>1 then m := n/2 {this is rough ½-way point} L := merge(sort(1,…, m), sort(m+1,…, n))return L Thuật toán trộn (trang tiếp) dùng Θ(n) bước, và sắp xếp trộn dùng Θ(n log n). Phương pháp trộn đệ quiRecursive Merge Method procedure merge(A,B: sorted lists){Given two sorted lists A=(a1,…,a|A|), B=(b1,…,b|B|), return a sorted list of all.} if A = () return B {If A is empty, it’s B.}if B = () return A {If B is empty, it’s A.}if a1<b1 return (a1,merge((a2,…a|A|),B))return (b1,merge(A,(b2,…,b|B|))) Chương trình trộnMerge Routine procedure merge(A, B: sorted lists)L = empty listi:=0, j:=0, k:=0while i<|A|  j<|B| {|A| is length of A} if i=|A| then Lk := Bj; j := j + 1 else if j=|B| then Lk := Ai; i := i + 1 else if Ai < Bj then Lk := Ai; i := i + 1 else Lk := Bj; j := j + 1 k := k+1return L Takes Θ(|A|+|B|) time Towers of Hanoi Towers of Hanoi Ở điểm này,chuyển đĩa lớn nhất. Tôi sẽ bắt đầu công việc. Thuật toán đệ qui Towers of Hanoi Time: T(1) = 1, T(n) = ≈ 2(2T(n-2)) ≈ 4(2T(n-3)) ≈ 2T(n-1) ≈ 4T(n-2) ≈ 8T(n-3) ≈ 2i T(n-i) ≈ 2n 1 + 2T(n-1)