tailieunhanh - CTDL 2005 chuong 6

Đệ 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 ngan xếp cho các lần gọi hàm Giả sử chung tá co 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 cuoi cung. Sự diên tiến cUá các hoát đọng cUá các hám xáy rá thêô tính chất váo sáu rá trươc Last In First Out -LIFO . Nếu xết đến nhiêm vu cuá máy tính trong viêc to chưc các vung nhơ tám dánh cho 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 trong một dánh sách co cung tính chất trên co nghĩá lá ngán xếp. Vì thế ngán xếp đong mot vái tro chu chot liến quán đến các hám trong hế thong máy tính. Trong 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 Cau truc 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 .