Đệ quy và không đệ quy
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (58 KB, 3 trang )
Duyệt đệ quy và không đệ quy
Nguyễn Duy Hàm
Phương pháp duyệt là một trong những phương pháp cơ bản để giải các bài toán trong Tin
học nhất là bài toán hữu hạn. Một khó khăn của pương pháp này là khi số cấu hình phải
duyệt trở lên quá lớn, nếu chúng ta không có phương án duyệt tốt sẽ không đáp ứng tốt
được yêu cầu của bài toán.
Khi tính toán việc cài đặt phương pháp duyệt ta thường nghĩ ngay tới mô hình quay lui.
Quay lui là mô hình có thể đảm bảo cho nguyên tắc không trùng lặp và bỏ sót của phương
pháp duyệt. Nội dung chính của phương pháp này là từng bước xây dựng dần các thành
phần của phương án bằng cách thử các khả năng có thể, nếu tồn tại một phương án chấp
nhận được thì tiến hành bước tiếp, nếu không thì lùi lại bước trước đó để xây dựng lại
phương án đó với các khả năng chưa được thử.
Giả sử một cấu hình là một véc tơ gồm n thành phần (x1, x2, x3,... xn) phải thỏa mãn một
điều kiện nào đó. Cụ thể mô hình này như sau:
Tại bước thứ i ta đã xây dựng xong i-1 thành phần (x1, x2,... xn-1), bây giờ ta phải xác
định thành phần thứ i của phương án. Lần lượt xét tất cả các khả năng của xi, lúc này xảy
ra các trường hợp sau:
+ Có một khả năng j thoả mãn ->xi được xác định theo khả năng này. Nếu i=n thì ta được
một nghiệm. Ngược lại i< tie^?p bu+o+?c ha`nh tie^?n>
+ Không có một khả năng nào chấp nhận được cho x1 -> lùi lại bước trước để xác định lại
thành phần xi-1.
Mô hình quay lui được tổ chức theo đệ quy dưới dạng giả mã như sau:
Procedure Duyet(i:Type_var);
Var j: Type_var;
Begin
For j do
If Then
Begin
[Ghi nhân trạng thái mới]
if i=n then
else Duyet(i+1);
[Trả lại trạng thái cũ]
End;
End;
Mô hình quay lui được cài đặt theo đệ quy rất hợp lí và thuận lợi. Tuy nhiên sử dụng đệ
quy dễ gây ra lỗi tràn Stack nhất là những bài toán đòi hỏi phải đệ quy khá sâu, cũng như
sử dụng nhiều biến trong thủ tục dệ quy. Mặt khác cơ chế gọi đệ quy của máy tính rất phức
tạp và mất thời gian. Vì vậy việc tìm ra một cơ chế khác cho mô hình quay lui là cần thiết.
Trên thực tế mọi bài toán đệ quy đều có thể đưa về lặp khử đệ quy. Mô hình chung của
phương pháp này như sau:
i:=1;
repeat
repeat
j:=<Miền khả năng cho xi>{nếu không tồm tại ->j=0}
if j>0 then
begin
if i=n then
begin
j:=0;
end;
i:=i+1;
end;
until j=0;
i:=i-1;
if i>0 then
until i=0;
Trong thực tế, nhiều bài toán miền xác định của xi phụ thuộc vào các khả năng đã được
xác định trước đó của x1, x2,... xi-1, vì vậy khi giải quyết các bài toán cụ thể cần có cách
lưu trạng thái của bài toán tại mỗi bước khi xác định thêm được một thành phần, phục vụ
cho việc xác định đúng đắn các thành phần tiếp theo, cũng như việc quay lui để xác định
lại thành phần đó.
