Cấu trúc dữliệu và giải thuật
Đố Bích Diệp- Khoa CNTT-ĐHBKHN 1
CấutrúcdữliệuvàGiảithuật
Chương II
Giải thuật đệ qui
Giải thuật đệ qui
Nội dung
Các khái niệm cơ bản
Một sốví dụ
Phân tích giải thuật đệ qui
Cấu trúc dữliệu và giải thuật
Đố Bích Diệp- Khoa CNTT-ĐHBKHN 2
Một số đối tượng đệ qui
Một số đối tượng đệ qui
zHàm đệ qui:
–Là hàm được xác định phụthuộc vào một biến
nguyên không âm n theo sơ đồ:
zBước cơ sở: xác định giá trịhàm tại một giá trịn giá trị
nhỏnhất có thểcủa biến
zBước đệ qui: Cho giá trị f(k) , đưa ra qui tắc để tính
f(k+1)
Cấu trúc dữliệu và giải thuật
Đố Bích Diệp- Khoa CNTT-ĐHBKHN 3
Một số đối tượng đệ qui
zTập hợp đệ qui
–Là tập được xác định như sau
zBước cơ sở: Định nghĩa tập cơ sở
zBước đệ qui: Xác định qui tắc để sản sinh tập mới từ
tập đã có
Một số đối tượng đệ qui
zĐịnh nghĩa đệ qui của xâu ký tự
–A = bảng chữcái, tập các xâu S trên bảng chữ
cái A được xác định
zXâu rỗng là xâu trong S
zNếu w thuộc S và x là một ký tựtrong A thì wx là xâu
trong S
Cấu trúc dữliệu và giải thuật
Đố Bích Diệp- Khoa CNTT-ĐHBKHN 4
Một số đối tượng đệ qui
zCây
–Định nghĩa đệ qui của cây
zMột nút tạo thành 1 cây
zNếu có n cây T1, T2, …, Tnvới nút gốc là r1, r2, … , rn; r
là một nút có quan hệcha-con r1, r2, … , rn thì tồn tại một
cây mới T nhận r làm gốc
Giải thuật đệ qui
–Định nghĩa: Giải thuật đệ qui là giải thuật được
định nghĩa sửdụng chính giải thuật có dạng
giống nó
–Cấu trúc của một thuật toán đệ qui bao gồm 2
bước
zBước cơ sở
–Với những giá trị đầu vào đủ nhỏ, bài toán có thểgiải quyết
trực tiếp
zBước đệ qui
–Lời gọi đến giải thuật đang định nghĩa
–Lời gọi đệ qui phải được định nghĩa để nó tiến gần hơn đến
bước cơ sở
Cấu trúc dữliệu và giải thuật
Đố Bích Diệp- Khoa CNTT-ĐHBKHN 5
Các dạng giải thuật đệ qui
–Đệ qui trực tiếp : AÆA
–Đệ qui gián tiếp: AÆB Æ…ÆA
–Đệ qui đuôi
zLời gọi đệ qui luôn luôn nằm cuối cùng trong giải thuật
Giải thuật đệ qui
–Ví dụ: Hàm tính n!
⎩
⎨
⎧
>−
=
=0)1(*
01
)( nifnFactn
nif
nFact
Function recursiveFactorial(n)
Begin
{Tính giá trịn! }
1. if n = 0 then return 1
else return n*FACT(n-1);
2. End.
Trường hợp cơ sở
Lời gọi đệ qui
Tổhợp kết quả