Bài giảng Kỹ thuật lập trình: Kỹ thuật lập trình đệ quy - ThS. Đặng Bình Phương

Chương trình trình bày về kỹ thuật lập trình đệ quy. Nội dung chính trong chương này gồm có: Tổng quan về đệ quy, các vấn đề đệ quy thông dụng, phân tích giải thuật & khử đệ quy, các bài toán kinh điển. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình: Kỹ thuật lập trình đệ quy - ThS. Đặng Bình PhươngBộmônCôngnghệphầnmềmKhoaCôngnghệthôngtinTrườngĐạihọcKhoahọcTựnhiên KỸTHUẬTLẬPTRÌNH ThS.ĐặngBìnhPhương dbphuong@fit.hcmus.edu.vn KỸTHUẬTLẬPTRÌNH ĐỆQUY 1 &&VCVC BB BB Nộidung 1 Tổng quan về đệ quy 2 Các vấn đề đệ quy thông dụng 3 Phân tích giải thuật & khử đệ quy 4 Các bài toán kinh điển Kỹthuậtlậptrìnhđệquy 2 &&VCVC BB BB Bàitoán  ChoS(n)=1+2+3+…+n =>S(10)?S(11)? S(10) = 11 + 22 + … + 10 10 = 55 55 S(11) = 11 + 22 + … + 10 10 + 11 11 = 66 66 = S(10) + 11 11 = 55 55 + 11 11 = 66 66 Kỹthuậtlậptrìnhđệquy 3 &&VCVC BB BB 2bướcgiảibàitoán Bước2.Thếngược ác định kết quả bài toán đồng S(n) = S(n1) + nn dạngtừ đơngiản đếnphứctạp Kếtquảcuốicùng. S(n1) = S(n2) + n1 n1 … = … + … … Bước1.Phântích S(1) = S(0) + 11 hân tích thành bài toán đồng dạngnhưngđơngiảnhơn. S(0) = 00 ừng lại ở bài toán đồng dạng đơn giản nhất có thể xác định ngaykếtquả. Kỹthuậtlậptrìnhđệquy 4 &&VCVC BB BB Kháiniệmđệquy Kháiniệm Vấnđềđệquylàvấnđềđược địnhnghĩabằngchínhnó. Vídụ TổngS(n)đượctínhthôngqua tổngS(n1). 2điềukiệnquantrọng Tồntạibướcđệquy. Điềukiệndừng. Kỹthuậtlậptrìnhđệquy 5 &&VCVC BB BB HàmđệquytrongNNLTC  Kháiniệm  Mộthàmđượcgọilàđệquynếubêntrong thâncủahàmđócólờigọihàmlạichínhnó mộtcáchtrựctiếphaygiántiếp. … Hàm(…) … Hàm1(…) … Hàm2(…) { { { … … … … … … Lời gọi Hàm Lời gọi Hàm2 Lời gọi Hàmx … … … … … … … … … } } } ĐQtrựctiếp ĐQgiántiếp Kỹthuậtlậptrìnhđệquy 6 &&VCVC BB BB Cấutrúchàmđệquy { (TS) Phầndừng if()(Basestep) { • Phầnkhởitínhtoánhoặcđiểm kếtthúccủathuậttoán … • Khôngchứaphầnđangđược return; địnhnghĩa } Phầnđệquy … (Recursionstep) …LờigọiHàm• Cósửdụngthuậttoánđang đượcđịnhnghĩa. … } Kỹthuậtlậptrìnhđệquy 7 &&VCVC BB BB Phânloại ...