Kỹ thuật khử đệ quy
Đệ quy là quả tim trong các nghiên cứu lý thuyết cũng như thực hành tính toán, đã thể hiện rất
nhiều sức mạnh và có ưu điểm trong nhiều bài toán. Tuy nhiên bài này tôi lại đi ngược với công
việc chúng ta thường làm: khử đệ quy, đó là vấn đề cũng có nhiều thú vị và đáng để chúng ta
xem xét.
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ực hành tính toán, đã thể hiện rất
nhiều sức mạnh và có ưu điểm trong nhiều bài toán. Tuy nhiên bài này tôi lại đi ngược với công
việc chúng ta thường làm: khử đệ quy, đó là vấn đề cũng có nhiều thú vị và đáng để chúng ta
xem xét.
Khử đệ quy ở đây là biến một thủ tục đệ quy thành một thủ tục chỉ chứa vòng lặp mà không ảnh
hưởng gì đế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ưng trong một số bài toán, đệ quy là bắt buộc. Bạn có thể nói rằng, vậy thì cứ sử dụng đệ quy,
vừa ngắn gọn dễ hiểu, vừa dễ cài đặt. Nhưng có đôi khi, sự hạn hẹp của bộ nhớ dành cho
chương trình con không cho phép chúng ta làm điều đó; hoặc chúng ta biết rằng, ngôn ngữ máy
khô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ật toá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ình nào.
Khử đệ quy thực chất là chúng ta phải làm công việc của một trì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ăn xếp
(Stack), quy định các giá trị tham số cho thủ tục và chuyển tới vị trí bắt đầu thủ tục, thực hiện lần
lượt từng câu lệnh. Sau khi thủ 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ển tớ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ài toán duyệt cây. Giả sử có một cây nhị
phân lưu trữ trong biến động t đượ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ốc t, cần duyệt qua hết cây theo thứ tự từ trái qua phải. Chương trình con đệ
quy sẽ như sau:
procedure Try(t : pnode);
begin
if t nil then
begin
visit(t);
Try(t^.l);
Try(t^.r);
end;
end;
