Đệ quy khử như thế nào
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 (81.62 KB, 5 trang )
Kỹ thuật khử đệ quy
Trần Đức Thiện
Đệ quy là quả tim trong các nghiên cứu lý thuyết cũng như thựchành tính toán, đã thể hiện
rất nhiều sức mạnh và có ưu điểmtrong nhiều bài toán. Tuy nhiên bài này tôi lại đi ngược
với côngviệc chúng ta thường làm: khử đệ quy, đó là vấn đề cũng có nhiềuthú vị và đáng
để chúng ta xem xét.
Khử đệ quy ở đây là biến mộtthủ tục đệ quy thành một thủ tục chỉ chứa vòng lặp mà không
ảnh hưởnggì đến các yếu tố khác, chứ không phải là thay đổi thuật toán. Vídụ như trong
các hàm đệ quy tính n! và số Fibonaci F(n) ta có thểthay bằng một vòng lặp để tính; Đó
không phải là phương pháp khửđệ quy mà tôi muốn nói. Trong trường hợp tổng quát, khử
đệ quy làmột việc làm khá phức tạp và khó khăn. ở hàm n! hay F(n) ta có thể dùng một
thuật toán không đệ quy, nhưngtrong một số bài toán, đệ quy là bắt buộc. Bạn có thể nói
rằng, vậythì cứ sử dụng đệ quy, vừa ngắn gọn dễ hiểu, vừa dễ cài đặt. Nhưngcó đôi khi, sự
hạn hẹp của bộ nhớ dành cho chương trình con khôngcho phép chúng ta làm điều đó; hoặc
chúng ta biết rằng, ngôn ngữ máykhông có đệ quy, vì vậy các trình biên dịch đều phải có
nhiệm vụkhử đệ quy. Và bạn có thể thực sự gặp rắc rối với thủ tục đệquy của mình khi
trong một môi trường lập trình mà không cung cấp khảnăng gọi đệ quy. Khử đệ quy giúp
bạn vẫn giữ được nguyên bản thuậttoán đệ quy của mình mà không hề có lời gọi đệ quy,
và như thếchương trình có thể chạy được trong bất kỳ môi trường lập trìnhnào.
Khử đệ quy thực chất là chúng ta phải làm công việc của mộttrình biên dịch đối với một
thủ tục, đó là: Đặt tất cả các giátrị của các biến cục bộ và địa chỉ của chỉ thị kế tiếp vào
ngănxếp (Stack), quy định các giá trị tham số cho thủ tục và chuyển tớivị trí bắt đầu thủ
tục, thực hiện lần lượt từng câu lệnh. Sau khithủ tục hoàn tất thì nó phải lấy ra khỏi ngăn
xếp địa chỉ trả vềvà các giá trị của các biến cục bộ, khôi phục các biến và chuyểntới địa chỉ
trả về.
Để dễ theo dõi chúng ta lấy ví dụ với bài toán cụ thể là bàitoán duyệt cây. Giả sử có một
cây nhị phân lưu trữ trong biến độngt được định nghĩa:
type pnode = ^node;
node = record
inf : variable; { truong luu tru thong tin }
l,r : pnode;
end;
var t : pnode;
Xuất phát từ nút gốct, cần duyệt qua hết cây theo thứ tự từ trái qua phải. Chương trìnhcon
đệ quy sẽ như sau:
procedure Try(t : pnode);
begin
if t <> nil then
begin
visit(t);
Try(t^.l);
Try(t^.r);
end;
end;
Trước hết có thể thấyrằng lệnh gọi đệ quy thứ hai có thể được khử dễ dàng bởi không
cómã lệnh theo sau nó. Khi lệnh này thực hiện thì thủ tục Try( ) đượcgọi với tham số t^.r
và khi lệnh gọi này kết thúc thì thủ tục Try hiệnhành cũng kết thúc. Chương trình được viết
lại như sau dùng goto:
procedure try(t : pnode);
label 0;
begin
0 : if t = nil then exit;
visit(t);
try(t^.l);
t := t^.r;
goto 0;
end;
Đó là kỹ thuật rấtnổi tiếng được gọi là khử đệ quy phần cuối. Việc khử lần gọiđệ quy còn
lại đòi hỏi phải làm nhiều việc hơn. Giống như một trìnhbiên dịch chúng ta phải tổ chức
một ngăn xếp (Stack) để lưu trữ cácbiến cục bộ, các tham số, vàsử dụng các thủ tục:
Push(t): Đặt biến t vàođỉnh Stack;
Hàm pop: lấy 1 giá trịở đỉnh stack.
Hàm stackempty: Báo hiệuStack đã rỗng.
ở đâykhông có giá trị trả về và chỉ có một biến cục bộ là t nên chúngta sẽ nạp nó vào stack
nếu chưa được xử lý và ở mỗi bước chúngta lấy biến ở đỉnh stack ra để xử lý nó và các nút
con tiếp theo củanó. Chương trình khử cả lời gọi đệ quy thứ hai sẽ như sau:
procedure try(t : pnode);
label 0,1,2;
begin
0: if t = nil then goto 1;
visit(t);
push(t);
t := t^.l;
goto 0;
2 : t := t^.r; goto 0;
1 : if stackempty then exit;
t := pop;
goto 2;
end;
Thủ tục trên chỉ làdiễn giải thô của ý tưởng để các bạn dễ hiểu, vì vậy các chỉ thịgoto còn
rườm ra, chúng ta sẽ viết lại một cách có cấu trúc hơn nhưsau:
procedure try(t : pnode);
label 0;
begin
0: while t <> nil do
begin
visit(t);
push(t^.r);
t := t^.l
end;
if stackempty then exit;
t := pop;
goto 0;
end;
Bây giờ, loại bỏhoàn toàn các chỉ thị goto và tránh trường hợp nạp các nút rỗng vàostack ta
có thủ tục duyệt cây không đệ quy chuẩn như sau, các bạn sẽthấy rằng về bản chất nó
không khác thủ tục đệ quy là mấy:
procedure try(t : pnode);
begin
push(t);
repeat
t := pop;
visit(t);
if t^.l <> nil then push(t^.l);
if t^.r <>nil then push(t^.r);
until stackempty;
end;
Để minh hoạ cụ thểhơn cho kỹ thuật này, tôi xin trình bày với các bạn chương trình sắpxếp
nhanh(QuickSort) khử đệ quy:
Program Quick_sort_Khu_de_quy_Th;
const inp = ′FileName.inp′;
out = ′FileName.out′;
maxstack = 1000;
maxn = 1000;
type it = longint;
var a : array[1..maxn] of it;
sl,sr: array[1..maxstack] of word;
n,top: it;
f: text;
procedurepush(l,r : word);
begin
inc(top);
sl[top] := l; sr[top] := r;
end;
procedurepop(var l,r : word);
begin
l := sl[top]; r := sr[top];
dec(top);
end;
functionstackEmpty : boolean;
begin
stackempty := top = 0;
end;
procedureinit;
begin
top := 0;
end;
procedurenhap;
var i : it;
begin
assign(f,inp); reset(f);
readln(f,n);
for i := 1 to n do read(f,a[i]);
close(f);
end;
proceduresort(l1,r1 : word);
var l,r,i,j: word;
t,tg : it;
begin
push(l1,r1);
repeat
pop(l,r);
i := l;
j := r;
t := a[(l+r) div 2];
repeat
while a[i] < t do inc(i);
while t < a[j] do dec(j);
if i <= j then
begin
tg:= a[i]; a[i] := a[j]; a[j] := tg;
inc(i); dec(j);
end;
until i > j;
if i < r then push(i,r);
if l < j then push(l,j);
until stackEmpty;
end;
procedurexuat;
var i : it;
begin
assign(f,out); rewrite(f);
for i := 1 to n do write(f,a[i],' ');
close(f);
end;
BEGIN
nhap;
init;
sort(1,n);
xuat;
END.
