Bài giảng Kỹ thuật lập trình: Đệ quy nâng cao, được biên soạn gồm các nội dung chính sau Nhận xét về đệ quy; Các bài toán kinh điển. Mời các bạn cùng tham khảo! | Đ quy nâng cao GV. Nguy n Minh Huy K thu t l p trình - Nguy n Minh Huy 1 N i dung Nh n xét v đ quy. quy. Các bài toán kinh đi n. n. K thu t l p trình - Nguy n Minh Huy 2 N i dung Nh n xét v đ quy. quy. Các bài toán kinh đi n. n. K thu t l p trình - Nguy n Minh Huy 3 Nh n xét v đ quy Khái ni m Call Stack void main main Vùng nh lưu tr ng thái A các hàm đang th c hi n. n. D Thông tin tr ng thái thái Tham s hàm. hàm. void A void C Bi n c c b . B V trí dòng l nh hi n hành. hành. C D void B void D STACK B B B C D A A A A A A A D M M M M M M M M M M M Th i gian K thu t l p trình - Nguy n Minh Huy 4 Nh n xét v đ quy L i Stack Overflow Tràn b nh Call Stack. Không th g i hàm thêm n a a Nguyên nhân nhân Công th c đ quy không h i t . S bư c đ quy quá l n. n. Kh đ quy quy Dùng vòng l p. p. Dùng ngăn x p. p. K thu t l p trình - Nguy n Minh Huy 5 Nh n xét v đ quy Khái ni m Call Tree Th hi n liên h gi a các hàm. hàm. main Giúp hình dung các bư c g i hàm. hàm. S nút t ng s l i g i hàm. nút hàm. Chi u cao kích thư c Call Stack. cao A D B C D K thu t l p trình - Nguy n Minh Huy 6 Nh n xét v đ quy Ưu đi m đ quy quy L i gi i đ quy nêu b n ch t v n đ Thu t toán rõ ràng sáng s a. ràng a. Chương trình ng n g n d hi u. n u. Nhi u bài toán ph c t p n u không dùng đ quy. quy. Gi m th i gian suy nghĩ. nghĩ. Đơn gi n hóa l p trình. trình. K thu t l p trình - Nguy n Minh Huy 7 Nh n xét v đ quy Khuy t đi m đ quy quy Các hàm đ quy l ng nhau nhau Gây khó khăn cho vi c debug. T n b nh lưu tr hàm. hàm. T c đ x lý ch m. m. Nhi u v n đ cài đ t đ quy không hi u qu . Nhi u bài toán không th gi i b ng đ quy. quy. Không nên l m d ng đ quy quy K thu t l p trình - Nguy n Minh Huy 8 N i dung Nh n xét v đ quy. quy. Các bài toán kinh đi n. n. K thu t l p trình - Nguy n Minh Huy 9 Các bài toán kinh đi n Tháp Hà N i i Bài toán toán Có 3 c t A B C. C t A có N đĩa theo th t l n dư i nh trên. i trên. Hãy chuy n N đĩa t c t A sang c t C M i l n chuy n 1 đĩa. đĩa. Đĩa nh luôn trên đĩa l . Có th dùng c t trung .
