Bài giảng Kỹ thuật lập trình: Đệ quy nâng cao - Nguyễn Minh Huy

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!
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình: Đệ quy nâng cao - Nguyễn Minh HuyĐ quy nâng cao GV. Nguy n Minh HuyK thu t l p trình - Nguy n Minh Huy 1N 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 2N 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 3Nh 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 gianK thu t l p trình - Nguy n Minh Huy 4Nh 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 5Nh 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 DK thu t l p trình - Nguy n Minh Huy 6Nh 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 7Nh 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 8N 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 9Cá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 n.n. Có th dùng c t trung gian. gian. 1 2 N C t ngu n A C t trung gian B C t đích CK thu t l p trình - Nguy n Minh Huy 10Các bài toán kinh đi n Tháp Hà N i: i: Áp d ng k thu t chia đ tr : Chuy n( N đĩa, A -> C, B trung gian ) n( đĩa, { if ( N == 1 ) L y A b qua C; else { / ...