Bài giảng Kỹ thuật lập trình - Chương 3: Kỹ thuật lập trình đệ quy - Trần Minh Thái

KỸ THUẬT LẬP TRÌNHChương 3Kỹ thuật lập trình đệ quyTRẦN MINH THÁI – minhthai@huflit.edu.vn, www.minhthai.edu.vn PHẠM ĐỨC THÀNH – phamducthanh@huflit.edu.vn, www.phamthao.com 12/3/20201Trần Minh Thái - Phạm Đức Thành3.1. Giới thiệu về lập trình đệ quy3.2. Phân loại các dạng đệ quy3.3. Hoạt động của đệ quy3.5. Xây dựng giải thuật đệ quy3.6. Các giải thuật đệ quy tiêu biểu3.7. Các giải pháp thay thế cho đệ quy3.8. Tóm tắt chương12/3/20202Trần Minh Thái - Phạm Đức ThànhNội dungKhi lập trình, gặp dạng bài toán: đối tượng khó định nghĩa một cách tường minh. Kỹ thuật định nghĩa đối tượng qua chính nó: kỹ thuật đệ quy (recursion). Ví dụ: 2 chiếc gương đối diện nhau. Chiếc thứ nhất chứa hình chiếc thứ hai và ngược lại. Ta hình dung ra dãy các ảnh vô hạn của hai chiếc gương.Ví dụ: trên truyền hình, biên tập viên ngồi kế bên màn hình của chương trình đang phát, có dãy hình ảnh lập đi lập lại nhưng nhỏ dần..12/3/20203Trần Minh Thái - Phạm Đức Thành[3.1] Giới thiệu về lập trình đệ quyĐệ quy được sử dụng rộng rãi trong khoa học máy tính và lý thuyết tính toán.Định nghĩa theo đệ quy của một khái niệm là định nghĩa khái niệm mới thông qua chính khái niệm đang muốn định nghĩa.Ví dụ: về các định nghĩa đệ quy như sau:Giai thừa của n (n!):Nếu n=0 hoặc n=1 thì n!=1.Nếu n>1 thì n!=(n-1)! * n12/3/20204Trần Minh Thái - Phạm Đức Thành[3.1] Giới thiệu về lập trình đệ quyKý hiệu số phần tử của một hữu hạn S là |S|:Nếu S= thì |S| = 0.Nếu S≠ thì chắc chắn có một phần tử xS, khi đó |S|=|S\{x}|+1.Đây là phương pháp định nghĩa tập hợp.Tập số tự nhiên:Số 1 là số tự nhiên (1N).Số tự nhiên bằng số tự nhiên cộng 1 (nN  (n+1)N).12/3/20205Trần Minh Thái - Phạm Đức Thành[3.1] Giới thiệu về lập trình đệ quyCấu trúc danh sách liên kết (linklist/xâu) kiểu T:Cấu trúc rỗng là danh sách liên kết kiểu T.Kết nối một thành phần kiểu T (nút kiểu T) vào một danh sách liên kết kiểu T, ta có một danh sách liên kết kiểu T.12/3/20206Trần Minh Thái - Phạm Đức Thành[3.1] Giới thiệu về lập trình đệ quyVí dụ trên, để định nghĩa đệ quy gồm 2 phần:Phần cố định (cơ sở - neo – anchor): các trường hợp suy biến (trường hợp đặc biệt) của thuật toán qua một điều kiện cụ thể (phần dừng của đệ quy – chương trình phải có tính dừng).Phần đệ quy (quy nạp): mô tả thuật toán trong trường hợp phổ biến qua chính đối tượng (gọi hàm đệ quy) một cách gián tiếp hay trực tiếp. Lưu ý: phần đệ quy phải tiến về phần không đệ quy.12/3/20207Trần Minh Thái - Phạm Đức Thành[3.1] Giới thiệu về lập trình đệ quyĐệ quy tuyến tínhĐệ quy nhị phânĐệ quy phi tuyếnĐệ quy hỗ tương12/3/20208Trần Minh Thái - Phạm Đức Thành[3.2] Phân loại đệ quyS, S*: xử lý không đệ quy. Có thể gộp bước 2.1 và 2.2 lại.12/3/20209Bước 1:Nếu thỏa điều kiện dừng thì thực hiện thao tác S (trả về kết quả)Bước 2:Ngược lại:Bước 2.1thực hiện lệnh S*Bước 2.2Gọi hàm đệ quy (cho đối tượng thường là nhỏ hơn)Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhĐệ quy tuyến tínhViết hàm tính giai thừa của n bằng cách dùng vòng lặpstatic int GiaiThua(int n){ ???}12/3/2020Trần Minh Thái - Phạm Đức Thành10Hàm tính giai thừa (n!)12/3/202011Bước 1:Nếu n=0 hoặc n=1 thì trả về 1Bước 2:Ngược lại: trả về n*Giai_thừa(n-1)Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhCài đặt:static int giaiThua(int n){ if (n == 1 || n == 0) return 1; return giaiThua(n - 1) * n;} 12/3/202012Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhĐệ quy tuyến tínhBài tập: Cho n là số nguyên dương, hãy viết hàm tính các tổng sau bằng phương pháp đệ quy:12/3/2020Trần Minh Thái - Phạm Đức Thành13Viết hàm tìm ước số chung lớn nhất của 2 số nguyên dương m và n bằng cách sử dụng vòng lặpstatic int UCLN (int m, int n){ ???} 12/3/202014Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhUớc chung lớn nhất của 2 số dựa vào thuật toán Euclide:12/3/202015Bước 1:Nếu n=0 thì trả về mBước 2:Ngược lại: trả về USCLN(n, m mod n)Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhCài đặt:static int uCLN(int m, int n){ if (n == 0) return m; return uCLN(n, m% n);}12/3/202016Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhĐệ quy tuyến tínhViết hàm xuất các phần tử lẻ trong mảng một chiều số nguyên bằng cách sử dụng vòng lặpstatic void XuatLe (int []a){ ???}12/3/2020Trần Minh Thái - Phạm Đức Thành17Liệt kê các giá trị lẻ của dãy số nguyên12/3/202018Bước 1:Nếu n=0 thì dừngBước 2:Ngược lại:Bước 2.1Nếu a[n-1] lẻ xuất A[n-1]Bước 2.2gọi hàm lietKeLe(a, n-1)Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhCài đặt:static void lietKeLe(int[] a, int n){ if (n == 0) return ; if (a[n - 1] % 2 != 0) Console.Write("{0,4}", a[n - 1]); lietKeLe(a, n - 1);}12/3/202019Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhKết quả xuất ra ngược với dãy ban đầu nhập vào.Xuất xuôi lại ta làm như sau:12/3/202020Bước 1:Nếu n=0 thì dừngBước 2:Ngược lại:Bước 2.1gọi hàm lietKeLe(a, n-1)Bước 2.2Nếu a[n-1] lẻ xuất A[n-1]Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhCài đặt:static void lietKeLe(int[] a, int n){ if (n == 0) return ; lietKeLe(a, n - 1); if (a[n - 1] % 2 != 0) Console.Write("{0,4}", a[n - 1]);}12/3/202021Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhĐệ quy tuyến tínhBài tậpViết hàm tìm vị trí xuất hiện cuối cùng của phần tử có giá trị x (nếu có) trong mảng một chiều số nguyên bằng phương pháp đệ quy. Viết hàm tìm vị trí xuất hiện đầu tiên của phần tử có giá trị x (nếu có) trong mảng một chiều số nguyên bằng phương pháp đệ quy.12/3/2020Trần Minh Thái - Phạm Đức Thành22Đối với hàm đệ quy không có trị trả về (void), ta có thể viết theo dạng sau12/3/202023Bước 1:Nếu chưa dừng (n>0) thì:Bước 1.1gọi hàm lietKeLe(a, n-1)Bước 1.2Nếu a[n-1] lẻ xuất A[n-1]Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhCài đặt:static void lietKeLe(int[] a, int n){ if (n > 0) { lietKeLe(a, n - 1); if (a[n - 1] % 2 != 0) Console.Write("{0,4}", a[n - 1]); }}12/3/202024Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhTính tổng giá trị của dãy số nguyên12/3/202025Bước 1:Nếu n=1 thì trả về a[n-1]Bước 2:Ngược lại: trả về a[n-1]+tongDay(a,n-1)Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhCài đặt:static int tongDay(int []a, int n){ if (n == 1) return a[n-1]; return a[n-1]+tongDay(a, n-1);}12/3/202026Trần Minh Thái - Phạm Đức ThànhĐệ quy tuyến tínhChương trình con gọi trực tiếp đến hàm đệ quy, thường sẽ có 2 lần gọi hàm đệ quy một cách tường minh với 2 nhánh rõ ràng.12/3/202027Trần Minh Thái - Phạm Đức ThànhĐệ quy nhị phânBước 1:Nếu thỏa điều kiện dừng thì thực hiện thao tác S (trả về kết quả)Bước 2:Ngược lại:Bước 2.1thực hiện lệnh S*Bước 2.2Gọi hàm đệ quy (đối tượng nhỏ hơn nhánh trái) lần thứ nhấtBước 2.3Gọi hàm đệ quy (nhánh phải) lần thứ hai12/3/202028Trần Minh Thái - Phạm Đức ThànhĐệ quy nhị phân12/3/202029Viết hàm fiBoNaCi(n) để tính số hạng thứ n của dãy Fibonaci.Bước 1:Nếu nright trả về -1Bước 2:B2.1:Tính mid=(left+right)/2B2.2:Nếu a[mid]=X thì trả về midB2.3:Nếu a[mid] right) return -1; int mid = (left + right) / 2; if (a[mid] == X) return mid; if (a[mid] 0) Yn = n2Xn-1 + Yn-1; (n>0) Điều kiện dừng:X(0) = Y(0) = 1.Trần Minh Thái - Phạm Đức ThànhĐệ quy hỗ tương12/3/202040static long TinhXn(int n){ if (n == 0) return 1; return TinhXn(n - 1) + TinhYn(n - 1);}static long TinhYn(int n){ if (n == 0) return 1; return n * n * TinhXn(n - 1) + TinhYn(n - 1);}Trần Minh Thái - Phạm Đức ThànhĐệ quy hỗ tương12/3/202041Gồm 2 pha:Pha tiến (forward): Tiến đến lời giải nhỏ nhất Pha lùi (backward): Kết hợp các kết quả lại với nhauTrần Minh Thái - Phạm Đức Thành[3.3] Hoạt động của đệ quy12/3/202042Main( )Gọi Giai thừa5Giai Thừa ( 5 )Gọi Giai thừa4Giai Thừa ( 4 )Gọi Giai thừa3Giai Thừa ( 3 )Gọi Giai thừa2Giai Thừa ( 2 )Gọi Giai thừa11! = 1n=5n=4n=3n=2n=1kq=120kq=24kq=6kq=2kq=1Trần Minh Thái - Phạm Đức Thành12/3/202043F4=F3+F2F0=1F1=1F0=1F1=1F1=1F2=F1+F0F2=F1+F0F3=F2+F1Trần Minh Thái - Phạm Đức Thành12/3/202044F4=F3+F2F0=1F1=1F0=1F1=1F1=1F2=F1+F0F2=F1+F0F3=F2+F1kq=1kq=1kq=1kq=2kq=1kq=1kq=2kq=3kq=5Trần Minh Thái - Phạm Đức Thành12/3/202045Bước 1: Thông số hóa bài toán.Bước 2: Phát hiện các trường hợp suy biến (đặc biệt, dừng, neo) và tìm giải thuật cho bài toán này.Bước 3: Phân rã bài toán theo hướng đệ quy.Trần Minh Thái - Phạm Đức Thành[3.4] Xây dựng giải thuật đệ quy12/3/202046Tổng quát hóa bài toán, tìm ra nhóm các bài toán, các thông số kích thước, thông số điều khiển.Ví dụ: thông số n trong hàm tính giai thừa, trong hàm Fibonaci, thông số a,b trong hàm tìm ước số chung lớn nhất...Trần Minh Thái - Phạm Đức ThànhBước 1: Thông số hóa bài toán12/3/202047Là các trường hợp tương ứng với giá trị biên của biến điều khiển (trường hợp kích thước nhỏ nhất, trường hợp đặc biệt) mà giải thuật không đệ quy giải rất đơn giản.Ví dụ: GiaiThua(1)=1.USCLN(a,0)=a. TSUM(a[m:m])=a[m].Trần Minh Thái - Phạm Đức ThànhB2: Phát hiện TH suy biến, tìm giải thuật12/3/202048Tìm giải thuật trong trường hợp tổng quát bằng cách phân rã thành các thành phần nhỏ hơn không đệ quy hoặc là bài toán đệ quy nhưng với kích thước nhỏ hơn.Trần Minh Thái - Phạm Đức ThànhBước 3: Phân rã theo hướng đệ quy12/3/202049B1: Thông hóa hóa bài toán:Xét ở mức tổng quát: chuyển n (n>0) đĩa từ cột A sang cột C với cột B làm trung gian.Ta gọi hàm có tên thapHaNoi(n,A,B,C) với bốn tham số, trong đó thông số n là thông số thay đổi, ta gọi n là thông số điều khiển.Trần Minh Thái - Phạm Đức ThànhBài toán tháp hà nội12/3/202050B2: Trường hợp suy biến và giải thuật:Với n=1 bài toán tổng quát suy biến thành bài toán đơn giản thapHaNoi(1,A,B,C), lúc này chỉ cần chuyển 1 đĩa từ cột A sang cột C là xong (trong đó B là cột trung gian), ta có thao tác chuyenDia(A,C).Trần Minh Thái - Phạm Đức ThànhBài toán tháp hà nội12/3/202051B3: Phân rã bài toán:Muốn n đĩa từ cột A sang cột C, với cột B là cột trung gian thapHaNoi, ta thực hiện 3 công việc sau:Chuyển (n-1) đĩa từ cột A sang cột B, lấy C làm trung gian: thapHaNoi(n-1,A,C,B)Chuyển 1 đĩa từ cột A sang cột C: chuyenDia(A,C) thao tác không đệ quy.Chuyển (n-1) đĩa từ cột B sang cột C, lấy A làm trung gian: thapHaNoi(n-1,B,A,C)Trần Minh Thái - Phạm Đức ThànhBài toán tháp hà nội12/3/202052Ta có giải thuật sau: thapHaNoi(n,A,B,C).Bước 1:Nếu chưa dừng (n>1) thìBước 1.1thapHaNoi(n-1,A,C,B)Bước 1.2chuyenDia(A,C)Bước 1.3thapHaNoi(n-1,B,A,C)Trần Minh Thái - Phạm Đức ThànhBài toán tháp hà nội12/3/202053static void chuyenDia(char A, char C){ Console.WriteLine("Chuyen tu dia {0} sang dia {1}", A, C); }static void thapHaNoi(int n,char A,char B,char C){ if(n>0) { thapHaNoi(n - 1, A, C, B); chuyenDia(A, C); thapHaNoi(n - 1, B, A, C); }}static void Main(string[] args){ thapHaNoi(3, 'A', 'B', 'C'); Console.ReadLine();}Trần Minh Thái - Phạm Đức Thành12/3/202054Backtracking – Quay luiThuật toán nhánh cậnThuật toán chia để trịTrần Minh Thái - Phạm Đức Thành[3.5] Các giải thuật đệ quy tiêu biểu12/3/202055Quay lui là PP thiết kế thuật toán để tìm nghiệm của bài toán bằng cách xét tất cả các phương án. Một phương án gồm nhiều thành phần, và phương pháp quay lui sẽ xây dựng từng thành phần trong mỗi bước. Trong quá trình xây dựng thành phần thứ i (tìm nghiệm cho thành phần thứ i), nếu không thể xây dựng được thì quay lại chọn nghiệm khác cho thành phần thứ (i-1)Trần Minh Thái - Phạm Đức ThànhĐịnh nghĩa [Quay lui – Backtracking]12/3/202056Phát biểu bài toán: Giả sử nghiệm của bài toán cần tìm có dạng X=(x1, x2, , xk, ), trong đó xi là 1 thành phần nghiệm của bài toán. xi có một miền giá trị Di nào đó (xi  Di). Số lượng thành phần xi có thể xác định hay không xác định. Bài toán có những ràng buộc là F.Yêu cầu: Hãy xây dựng 1 nghiệm hay tất cả các nghiệm của bài toán thỏa điều kiện F. Trần Minh Thái - Phạm Đức ThànhQuay lui – Backtracking12/3/202057Phương pháp Quay lui xây dựng dần nghiệm X của bài toán: Bắt đầu từ x1 được chọn ra từ tập D1, rồi đến x2 được chọn ra từ tập D2, ... bằng cách thử mọi khả năng có thể xảy ra.Một cách tổng quát: Nếu chúng ta đã xác định được lời giải bộ phận gồm (i-1) thành phần X(i-1) = (x1, x2, ..., xi-1), bây giờ chúng ta tìm giá trị cho thành phần xi bằng cách xét mọi khả năng có thể có của xi trong tập Di. Với mỗi khả năng j (jDi), chúng ta kiểm tra xem có thể thỏa điều kiện là nghiệm thành phần của bài toán không. Trần Minh Thái - Phạm Đức ThànhPhương pháp Quay lui 12/3/202058Có 2 khả năng xảy ra:Nếu khả năng j thỏa điều kiện thì Gán xi = j Tiếp theo tìm nghiệm cho thành phần xi+1 Nếu đã thử mọi khả năng của j mà không thỏa điều kiện bài toán thì con đường X(i-1) = (x1, x2, ..., xi-1) không thể dẫn đến kết quả. Chúng ta quay về bước trước để xác định lại xi-1 (bằng cách chọn 1 giá trị khác trong Di-1).Trần Minh Thái - Phạm Đức ThànhPhương pháp Quay lui 12/3/202059Quá trình này dừng cho đến khi tìm được nghiệm của bài toán hay vét qua hết khả năng mà không thể tìm được nghiệm của bài toán.Trần Minh Thái - Phạm Đức ThànhPhương pháp Quay lui 12/3/202060Cây tìm kiếm (Cây không gian tìm kiếm): Quá trình tìm kiếm lời giải theo phương pháp Quay lui sẽ sinh ra 1 cây tìm kiếmx1x2x3Trần Minh Thái - Phạm Đức ThànhPhương pháp Quay lui 12/3/202061Xây dựng dần từng thành phần trong 1 phương án Trong quá trình xây dựng phương án nó thực hiện: Tiến: Để mở rộng các thành phần của phương án Lui: Nếu không thể mở rộng phương án Xét mọi khả năng có thể xảy ra Phương pháp quay lui còn được gọi với những tên khác như: Vét cạn (Exhaustion), Duyệt, thử và sai (Trial and Error), Trần Minh Thái - Phạm Đức ThànhĐặc điểm của phương pháp Quay lui12/3/202062Bước 1 [Biểu diễn nghiệm]: Biểu diễn nghiệm bài toán dưới dạng một vector  X=(x1, x2, x3, , xk, )Bước 2 [Tìm miền giá trị thô]: Xác định các miền giá trị cơ bản Di cho các xi (Di=[mini, maxi])Bước 3 [Ràng buộc]: Tìm những ràng buộc của xi và giữa xi và xj. Từ đó có thể xác định lại các Di Bước 4: Xác định những điều kiện F khác để X là nghiệm của bài toánTrần Minh Thái - Phạm Đức ThànhCác bước sử dụng PP Quay lui12/3/202063void BackTrack_1A(int i){ if (thỏa điều kiện bài toán F) Tìm được 1 nghiệm else for (j  Di) { xi = j; BackTrack_1A(i+1); }}Trần Minh Thái - Phạm Đức ThànhDi và Dj độc lập nhau12/3/202064void BackTrack_1B(int i){ for (j  Di) { xi = j; if (thỏa điều kiện bài toán F) Tìm được 1 nghiệm else BackTrack_1B(i+1); }}Trần Minh Thái - Phạm Đức ThànhDi và Dj độc lập nhau12/3/202065void BackTrack_2A(int i){ if (thỏa điều kiện bài toán F) Tìm được 1 nghiệm else for (j  Di và status[j]==0) { status[j] = 1; xi = j; BackTrack_2A(i+1); status[j]=0; }}Trần Minh Thái - Phạm Đức ThànhDi và Dj phụ thuộc nhau12/3/202066void BackTrack_2B(int i){ for (j  Di và status[j]==0) { status[j]=1; xi = j; if (thỏa điều kiện bài toán F) Tìm được 1 nghiệm else BackTrack_2B(i+1); status[j]=0; }}Trần Minh Thái - Phạm Đức ThànhDi và Dj phụ thuộc nhau12/3/202067Một tổ hợp chập k của tập n phần tử (k≤n) là một tập hợp con gồm k phần tử của tập n phần tử Với tập {1, 2, 3, 4, 5} ta có các tổ hợp chập 3 là:{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}.Số lượng tổ hợp chập k của tập n phần tử:Trần Minh Thái - Phạm Đức ThànhBài toán tổ hợp12/3/202068Các bước: tìm tổ hợp chập k của tập n phần tử Bước 1: Biểu diễn nghiệm XX=(x1, x2, x3, , xk)Bước 2: Tìm miền giá trị Di của xi xi (Di=[ xi-1+1, n-k+i])Bước 3: Ràng buộc giữa xi và xj xi f(X) thì ta lưu nghiệm tốt hơn lại. Xt = XFt = f(X)Trần Minh Thái - Phạm Đức ThànhPP Nhánh cận (Branch and bound)12/3/202078Bước 3 [Nhánh cận]:Trong quá trình xây dựng nghiệm, giả sử đã xây dựng được nghiệm gồm k thành phần X=(x1, x2, , xk). Bây giờ ta dự định mở rộng nghiệm thành (x1, x2, , xk, xk+1) nhưng nếu ta biết rằng những nghiệm mở rộng (x1, x2, , xk, xk+1, ) không thể tốt hơn Ft (nghĩa là g(x1, x2, , xk, xk+1, ) > Ft) thì ta không cần mở rộng (x1, x2, , xk), chúng ta cắt đi những nghiệm (nhánh) không cần thiết.Trần Minh Thái - Phạm Đức ThànhPP Nhánh cận (Branch and bound)12/3/202079Nhận xét Phương pháp nhánh cận không quét qua toàn bộ các nghiệm có thể có của bài toán Khó khăn của phương pháp nhánh cận là làm thế nào đánh giá được các nghiệm mở rộng (cận). Nếu đánh giá tốt sẽ bỏ nhiều nghiệm không cần thiết phải xét (nhánh)Trần Minh Thái - Phạm Đức ThànhPP Nhánh cận (Branch and bound)12/3/202080void BranchAndBound1(int i){ if (thỏa điều kiện bài toán F) { Tìm được một nghiệm Cập nhật Xt và Ft }  else  for (j  Di) { xi = j; if (g(x1, x2, , xi) 0 && V[j]==0) { X[i] = j; V[j] = 1; if (i == Arr.GetLength(0) - 1) { Print(X, Arr.GetLength(0)); Ft = cost + Arr[i, j]; Console.WriteLine("Cost=" + Ft); } else if (cost + Arr[i, j] = 0 && A[j] > tam) { A[j + 1] = A[j]; j--; } A[j + 1] = tam;}static void insertionSort(int[] A, int i){ if (i > 0) { insertionSort(A, i - 1); chenSapTang(A, i); }}Trần Minh Thái - Phạm Đức Thành12/3/202095Đệ quy là phương pháp giúp ta tìm giải thuật cho các bài toán khó. Giải thuật đệ quy thường rất gọn gàng, dễ hiểu, dễ chuyển thành chương trình. Tuy nhiên các giải thuật đệ quy thường tốn không gian bộ nhớ và thời gian thực thi. Hơn nữa, có một số ít ngôn ngữ lập trình không cho phép đệ quy. Vì vậy, việc khử đệ quy là vấn đề cần quan tâm.Trần Minh Thái - Phạm Đức ThànhCác giải pháp thay thế cho đệ quy12/3/202096Ví dụ: Tính tổng S(n)=1+2+..+n, với n>0.static int tongDeQuy(int n){ if (n == 1) return 1; return n + tongDeQuy(n - 1);}static int tongS(int n){ return n * (n + 1) / 2;}Trần Minh Thái - Phạm Đức ThànhTìm công thức không đệ quy12/3/202097Ví dụ: Tính tổng S(n)=1+2+..+n, với n>0.static int tongVongLap(int n){ int S = 0; for (int i = 1; i S, int n){ if (n == 0 || n == 1) return 1; S.Push(1);S.Push(1); for(int i=2; i<= n; i++) { int f2 = S.Pop(); int f1 = S.Pop(); int fn = f2 + f1; S.Push(f2); S.Push(fn); } return S.Pop();}Trần Minh Thái - Phạm Đức ThànhDùng stack để mô phỏng đệ quy12/3/2020102Một hàm được gọi có tính đệ qui nếu trong thân của hàm đó có lệnh gọi lại chính nó một cách tường minh hay tiềm ẩn.Phân loại đệ quiĐệ qui tuyến tính.Đệ qui nhị phân.Đệ qui phi tuyến.Đệ qui hỗ tương.Trần Minh Thái - Phạm Đức ThànhTóm tắt chương12/3/2020103Hoạt động đệ quy gồm 2 pha: pha tiến và pha lùi.Ta có ba bước để xây dựng giải thuật đệ quy:Thông số hóa.Tính trường hợp đặc biệt, dừng (suy biến – neo – cố định)Tính trường hợp tổng quát (câu lệnh và gọi đệ quy).Trần Minh Thái - Phạm Đức ThànhTóm tắt chương12/3/2020104Có một số giải thuật đệ quy tiêu biểu như: quay lui, nhánh cận và chia để trị.Ta có thể dùng các giải pháp thay thế cho đệ quy như:Dùng công thức tường minh, vòng lặp.Dùng mảng 1 chiều, 2 chiều.Dùng Stack.Trần Minh Thái - Phạm Đức ThànhTóm tắt chương12/3/2020105Tính n!In ra các ước số của số nguyên dươngĐếm số lượng ước số của số nguyên dươngTìm ước số chung lớn nhất của 2 số nguyên dương Kiểm tra số nguyên dương n có phải là số nguyên tố? Nhập vào mảng 1 chiều số nguyên a, kích thước nXuất mảng 1 chiều số nguyên a, kích thước nTrần Minh Thái - Phạm Đức ThànhBài tập12/3/2020106Tìm phần tử có giá trị x trong mảng số nguyên a, kích thước nViết hàm đệ quy tính tổ hợp chập k của n.Viết hàm đệ quy In mảng a gồm n phần tử (n≤100) lên màn hình Viết hàm đệ quy In ra các chữ số của số nguyên n theo thứ tự đảo ngược Viết hàm đệ quy Tìm số lớn nhất /nhỏ nhất của mảng số nguyên a có n phần tử (n≤100).Trần Minh Thái - Phạm Đức ThànhBài tập12/3/2020107Viết hàm đệ quy đếm số lần xuất hiện của ký tự ch trong chuỗi sViết hàm đệ quy Kiểm tra n có phải là số nguyên tố không Viết hàm đệ quy Giải bài toán tháp HanoiViết hàm đệ quy liệt kê các phân số tối giản không giảm nằm trong [0, 1] và có mẫu số nhỏ hơn hay bằng nViết hàm đệ quy Tính giá trị của một số viết dưới dạng chữ LA MÃ.Viết hàm đệ quy cho bài toán mã đi tuần.Trần Minh Thái - Phạm Đức ThànhBài tập