Chương 6: Lập trình Hàm

Một hàm được gọi là đệ quy nếu bên trong thâncủa hàm đó có lời gọi hàm lại chính nó một cáchtrực tiếp hay gián tiếp.Cơ chế gọi hàm dùng STACK trong C phù hợpcho giải thuật đệ quy vì: Lưu thông tin chương trình còn dở dang mỗi khigọi đệ quy. Thực hiện xong một lần gọi cần khôi phục thôngtin chương trình trước khi gọi. Lệnh gọi cuối cùng sẽ hoàn tất đầu tiên.
Nội dung trích xuất từ tài liệu:
Chương 6: Lập trình Hàm Chương6:LậptrìnhHàm (Phần2)02/2012 Nộidung 1 Tổng quan về đệ quy 2 Các vấn đề đệ quy thông dụng 3 Các bài toán kinh điển 4 Phân tích giải thuật & khử đệ quy Kỹthuậtlậptrìnhđệquy02/2012 2 Bàitoán • ChoS(n)=1+2+3+…+n =>S(10)?S(11)? S(10) = 1 + 2 + … + 10 = 55 S(11) = 1 + 2 + … + 10 + 11 = 66 = S(10) + 11 = 55 + 11 = 66 Kỹthuậtlậptrìnhđệquy02/2012 3 2bướcgiảibàitoán Bước2.Thếngược ác định kết quả bài toán đồng = S(n1) + n S(n) dạng từ đơn giản đến phức tạp Kếtquảcuốicùng. = S(n2) + n1 S(n1) = +… … … Bước1.Phântích = +1 S(1) S(0) hân tích thành bài toán đồng =0 S(0) dạngnhưngđơngiảnhơn. ừ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đệquy02/2012 4 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đệquy02/2012 5 HàmđệquytrongNNLTC • Kháiniệm – Mộthàmđượcgọilàđệquynếubêntrongthân củahàmđócólờigọihàmlạichínhnómộtcách trự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àm1 … … … … … … … … … } } } ĐQtrựctiếp ĐQgiántiếp Kỹthuậtlậptrìnhđệquy02/2012 6 Cấutrúchàmđệquy (TS)ừng { Phầnd 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đệquy02/2012 7 Phânloại Trong thân hàm có duy nhất một lời gọi hàm gọi lại chính nó một 1 TUYẾN TÍNH ...