tailieunhanh - Chương 6 " Đệ quy"

Nếu lời giải của một bài toán P được thực hiện bằng lời giải của bài toán P’ có dạng giống như P thì đó là một lời giải đệ quy. Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ quy. | Chương 6 - Đệ quy Chương 6 - ĐỆ QUY Chương này trình bày về đệ quy recursion - một phương pháp mà trong đó để giài một bài toàn ngươi tà giài các trương hợp nhó hơn cUà nó. Chung tà càn tìm hiệ9u một vài ưng dung và chương trình màu đệ9 thấy đươc một só trong rất nhiều dàng bài toàn mà việc sử dung đệ quy để giài rất có lơi. Một so ví du đơn giàn một số khàc thực sự phưc tàp. Chung tà cung sệ phàn tích xệm đệ quy thương đươc hiện thưc tróng mày tính như thế nàó khi nàó nện dung đệ quy và khi nàó nện trành. . Giới thiệu vế đệ quy . Cơ cấu ngăn xếp cho các lan gọi hàm Khi một hàm gội một hàm khàc thì tất cà càc tràng thài mà hàm gội đàng có càn đươc khói phục lài sàu khi hàm đươc gội kết thuc đệ9 hàm này tiếp tuc thưc hiện cóng việc dơ dàng cuà mình. Tràng thài đó góm có điệ9m quày vệ dóng lệnh kế sàu lệnh gội hàm càc trị tróng càc thành ghi vì càc thành ghi tróng bộ xử ly sệ đươc hàm đươc gội sử dung đến càc trị tróng càc biến cuc bộ và càc thàm trị cuà nó. Như vày mói hàm càn có một vung nhơ dành riệng chó nó. Vung nhơ này phài đươc tón tài tróng suết thơi giàn kệ từ khi hàm thưc hiện chó đốn khi nó kết thuc cóng việc. Time---- Hình Cơ cấu ngàn xệp chó càc làn gội hàm Già sử chung tà có bà hàm A B C mà A gội B B gội C. B sệ khóng kết thuc trươc khi C kết thuc. Tương tự A khơi sự cóng việc đàu tiện nhưng lài kết thuc cuóì cung. Sự diện tiện cuà càc hóàt động cuà càc hàm xày rà thệộ tính chất vàó sàu rà trươc Last In First Out -LIFO . Neu xệt đốn nhiệm vu cuà mày tính tróng việc tộ chưc càc vung nhơ tàm dành chó càc hàm này sử dung chung tà thấy ràng càc vung nhơ này cung phài nàm tróng một dành sàch có cung tính chất trện có nghĩà là ngàn xếp. Vì thế ngàn xếp đóng một vài trộ chu chót liện quàn đến càc hàm tróng hệ living mày tính. Tróng hình M biếu diện chương trình chính A B C là càc hàm trện. Giao trình Cấu trúc dư liệu và Giải thuật 91 Chương 6 - Đệ quy Hình biểu diễn một day các vùng nhớ tạm cho các hàm mỗi cột là hình ảnh cùà ngàn xếp tại