Kỹ thuật khử đệ quy

Chia sẻ: Cao Chi Chinh | Ngày: | Loại File: DOC | Số trang:3

0
317
lượt xem
122
download

Kỹ thuật khử đệ quy

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đệ 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.

Chủ đề:
Lưu

Nội dung Text: Kỹ thuật khử đệ quy

  1. Kỹ thuật khử đệ quy Trần Đức Thiện
  2. Đệ 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; 
Đồng bộ tài khoản