Đệ quy và cách khử

Giải thuật khử đệ quy

Nguyễn Văn Trường

Các khái niệm về đệ quy (ĐQ), giảithuật đệ quy (GTĐQ) được gặp nhiều trong tin học.

GTĐQ được dùng khá phổ biếnđể giải các bài toán tính các công thức hồi quy, các bài toán

khoa học kỹ thuậtvà đặc biệt được dùng nhiều trong cấu trúc dữ liệu cây. Hiện nay một số

ngônngữ lập trình phổ biến như: Pascal, PL1... cho phép gọi các thủ tục ĐQ (phươngtiện

để thể hiện GTĐQ), nên việc cài đặt các GTĐQ đã trở lên khá dễ dàng, cóhiệu quả và phản

ánh rất sát nội dung của định nghĩa ĐQ. Tuy nhiên, điều đókhông có nghĩa là đảm bảo

rằng GTĐQ là cách tốt nhất để giải bài toán,bởi vì quá trình dịch GTĐQ trong các ngôn

ngữ cho gọi thủ tục ĐQ tốn nhiềuthời gian và bộ nhớ hơn. Do đó, chúng ta sẽ nghiên cứu

vấn đề chuyểncác GTĐQ bằng các giải thuật không tự gọi chúng (không ĐQ) hay còn gọi

là giảithuật khử ĐQ (GTKĐQ).

Sau đây là mộtví dụ đơn giản sử dụng giải thuật lặp để tính số hạng thứ n của dãy

sốFibonacithay cho GTĐQ tương ứng:

Function F(n:Byte): Longint; { GTĐQ }

Begin

If n < 3 then F: = 1

Else F: = F(n-1) + F(n - 2);

End;

Function F(n: Byte): Longint; { GTKĐQ }

Var F1,F2 : longint;i: Byte;

Begin

If n < 3 then F: = 1

Else Begin

F1: = 1; F2 =1; i: = 2;

Whilei < n do

Begini: = i + 1; F2: = F1 + F2; F1: = F2 - F1; End;