Cấu trúc dữ liệu và giải thuật
Chương III: Giải thuật đệ quy

Chương III. GIẢI THUẬT ĐỆ QUY
I. KHÁI NIỆM VỀ ĐỆ QUY
II. GIẢI THUẬT ĐỆ QUY VÀ THỦ TỤC ĐỆ QUY
III. THIẾT KẾ GIẢI THUẬT ĐỆ QUY
IV. HIỆU LỰC CỦA ĐỆ QUY
V. BÀI TẬP

I. Khái niệm đệ qui
Ta nói một đối tượng là đệ
qui nếu nó được định nghĩa
qua chính nó hoặc một đối
tượng khác cùng dạng với
chính nó bằng qui nạp.

Ví dụ đệ qui
o
Số tự nhiên

1 là số tự nhiên_phần neo

x là số tự nhiên nếu x-1 là số tự nhiên_ phần đệ qui.
o
Hàm n!

Ứng với n=0 thì 0! = 1_phần neo

Nếu n>1 thì n! = n(n-1)!_phần đệ qui.
Sau mỗi lần đệ quy giá trị n giảm đi 1 và bài toán dần tới


II.Giải thuật đệ qui và thủ tục đệ qui
1. GIẢI THUẬT ĐỆ QUI

Nếu lời giải của bài toán T được thực
hiện bằng lời giải của bài toán T’ giống T
thì đó được gọi là một lời giải đệ quy.
Giải thuật cho lời giải đệ quy được gọi là
một giải thuật đệ quy.

Chú ý T’<T

VÍ DỤ:TÌM TỪ TRONG TỪ ĐiỂN
IF từ điển là 1 trang
then tìm từ trong trang này [ phần suy biến]
Else begin [ phần đệ qui]
Mở từ điển vào trang giữa;
Xác định xem nửa nào của từ điển chứa từ
cần tìm;
If nằm ở nửa trước của từ điển.
Then tìm từ đó trong nửa trước.
Else tìm từ đó trong nửa sau.
End;

  ụ ế

  ừ ầ

Ta thấy có điểm lưu ý trong phần đệ qui, sau
môi lần tách đôi từ điển thì một nửa thích hợp

chính nó
Đệ qui Phi tuyến:thân hàm lặp gọi 1
số lần chính nó


Ví dụ : thủ tục tìm từ trong từ điển

Di được coi là đầu mối để truy cập vào từ điển đang xét,
word chỉ từ cần tìm.
If từ điển chỉ còn một trang
Then tìm từ word trong trang này
Else begin
Mở từ điển vào trang giữa;
Xác định xem nửa nào của từ điển chứa từ word;
If nằm ở nửa trước của từ điển.
Then tìm từ word trong nửa trước.
Else tìm từ word trong nửa sau.
Then call SEARCH (Di 1, word)
Else call SEARCH (Di 2, word)
End;

Nhận xét

Tồn tại một trường hợp suy biến gọi là
giá trị neo làm kết thúc giải thuật đệ quy.

+ Trong phần thủ tục chứa lời gọi tới
chính nó.(thủ tục search có call search)

+ Sau mỗi lần gọi thì kích thước bài

7
!"#$%&'()*'+ )Ậ
!,+-.
!"#$%&'+&/+#' $Ộ
!0123 4$"%'5,,$Ố
!"#$%&'6
III. THIẾT KẾ GIẢI THUẬT ĐỆ QUY
7
1.Hàm n!

Định nghĩa đệ quy của n!
factorial (n)
=


7
1. Hàm n!

Thủ tục hàm:

Function FACTORIAL(n)
1. If n=0 then FACTORIAL:=1
else
FACTORIAL:=n*FACTORIAL(n-1)
2. Return
7
1. Hàm n!
Ví dụ: Tính 3!
3! = 3*2!
2!=2*1!

Tháng thứ 5: 5 cặp (cặp con bắt đầu đẻ)
7
89 ứ
Tháng thứ2
Tháng thứ3
Tháng thứ 4
Tháng thứ 5
7