Bài giảng Nhập môn lập trình - Chương 16: Kỹ thuật lập trình đệ quy

Chương 16 trang bị cho người học những hiểu biết về kỹ thuật lập trình đệ quy. Trong chương này chúng ta sẽ cùng tìm hiểu một số nội dung cơ bản sau: Tổng quan về đệ quy, các vấn đề đệ quy thông dụng, phân tích giải thuật và khử đệ quy, các bài toán kinh điển. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn lập trình - Chương 16: Kỹ thuật lập trình đệ quy &&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 NMLTKỹthuậtlậptrìnhđệquy 1 &&VCVC BB BB Bàitoán  Cho S(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 NMLTKỹthuậtlậptrìnhđệquy 2 &&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ả. NMLTKỹthuậtlậptrìnhđệquy 3 &&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. NMLTKỹthuậtlậptrìnhđệquy 4 &&VCVC BB BB HàmđệquytrongNNLTC  Khái niệm  Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách trực tiếp hay gián tiế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 NMLTKỹthuậtlậptrìnhđệquy 5 &&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. … } NMLTKỹthuậtlậptrìnhđệquy 6 &&VCVC BB BB Phânloại Trong thân hàm có duy nhất một TUYẾN TÍNH 1 lời gọi hàm gọi lại chính nó một cáchtườngminh. Trong thân hàm có hai lời gọi NHỊ PHÂN 2 hàm gọi lại chính nó một cách ...