1. KHÁI NIỆM
- Một đối tượng gọi là đệ qui nếu có bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng chính nó.
■ Ví dụ:
a) Số tự nhiên:
• 1 là một số tự nhiên.
• X là số tự nhiên nếu x - 1 là số tự nhiên.
b) Hàm n giai thừa: n !
• 0 ! = 1
• Nếu n > 0 thì n ! = n(n - 1) !
2. THỦ TỤC ĐỆ QUI
- Một thủ tục được gọi là đệ qui nếu trong quá trình thực hiện nó có phần phải gọi đến chính nó nhưng với kích thước nhỏ hơn của tham số.
■ Ví dụ: Function GT (n: word) : longint;
Begin
if n := 0 then GT := else
GT := n*GT(n - 1);
end;
3. CẤU TRÚC CỦA MỘT THỦ TỤC ĐỆ QUI
Một thủ tục đệ qui luôn gồm hai phần:
- Phần neo: Trong đó chứa các tác động của hàm hoặc thủ tục với một sô giá trị cụ thể ban đầu của tham số.
■ Ví dụ:
if n := 0 then GT := 1
- Phần hạ bậc: Trong đó tác động cần được thực hiện cho giá trị hiện thời của các tham số được định nghĩa bằng các tác động đã được định nghĩa trước đây.
■ Ví dụ:
GT := n*GT(n - 1)
4. ƯU ĐIỂM CỦA ĐỆ QUI
1. Đệ qui mạnh ở chỗ có thể định nghĩa một tập rất lớn các tác động chỉ bởi một số hữu hạn các mệnh đề.
2. Rất thích hợp để giải các bài toán có bản chất đệ qui.
3. Một chương trình viết theo giải thuật có tính đệ qui sẽ mang tính “Người” hơn, do đó sẽ:
- Sáng sủa.
- Dễ hiểu.
- Nêu bật được bản chất của vấn đề.
4. Có nhiều bài toán mà việc nghĩ ra lời giải đệ qui thường dễ hơn nhiều so với việc nghĩ ra lời giải dùng vòng lặp.
5. Khử đệ qui:
- Có một số giải thuật đệ qui thuộc loại tính toán đơn giản có thể được thay thế bởi một giải thuật khác không tự gọi chúng, sự thay thế đó được gọi là khử đệ qui.
- Tuy nhiên điều trên không có nghĩa là phải khử đệ qui bằng mọi giá và không nên e ngại cũng như có ác cảm với việc dùng đệ qui.
■ Ví dụ 1: Thủ tục đệ qui sau:
Function GT (n: word) : longint;
Begin
if n := 0 then GT := 1 else
GT := n * GT (n - 1);
end;
- Có thể được khử đệ qui như sau:
Function GT (n: word): longint;
Var
i: word ;
T: longint ;
Begin
T := 1
if n > 0 then
For i := 1 to n do T: = t * i;
GT:= T;
end;
Ví dụ 2: Thủ tục đệ qui
Function Fib (n: integer): integer;
Begin
if n := 0 then Fib := 0 else
if n:= 1 then Fib := 1
else Fib := Fib(n - 1) + Fib(n - 2);
end;
- Có thể được khử đệ qui như sau:
Function Fib (n: integer): integer;
Var
i, x, y: integer;
Begin
if n := 0 then Fib := 0 else
if n := 1 then Fib := else
Begin
i := 1; y := 0; x := 1;
while i < 0 do
Begin
i := i + 1
x := x + y
y := x - y
end;
Fib := x;
end;
end;
5. ĐỆ QUI VÀ QUAY LUI
- Trong lập trình, phương pháp giải một bài toán tổng quát rất được chú ý. Đó là việc xác định các giải thuật để tìm lời giải cho một số bài toán nào đó không phải theo một luật tính toán cố định mà bằng phương pháp “thử và sai” (Try anf Error).
- Thông thường là ta phân tích quá trình thử và sai thành các công việc cục bộ dưới dạng một cây tìm kiếm và ta phải từng bước duyệt cây tìm kiếm đó một cách đệ qui theo cấp của cây.
- Trong nhiều bài toán, cây tìm kiếm này lớn lên rất nhanh theo hướng hàm mũ và công sức tìm kiếm cũng tăng theo với sự lớn lên của cây.
- Trong thực tế ta phải tỉa cây tìm kiếm bằng các cách Heuristic và như vậy ta đã làm giảm công sức tính toán tới một giới hạn có thể chấp nhận được.
- Nét đặc trưng của phương pháp này là ở chỗ các bước đi đến lời giải hoàn toàn bằng cách làm thử. Nếu có một lựa chọn được chấp nhận thì ghi nhớ các thông tin cần thiết và tiến hành các bước thử tiếp theo. Nếu trái lại không có một lựa chọn nào thích hợp cả thì làm lại bước trước, xóa bớt các ghi nhớ và quay về chu trình thử với các lựa chọn còn lại. Hành động này được gọi là quay lui (Back tracking) và các giải thuật thế hiện phương pháp này gọi là các giải thuật quay lui.
- Hơn nữa nếu ở mỗi bước số những nước có thể đi là m thì ta có thể dùng một tham số để chỉ độ sâu của sự đệ qui và như thê làm đơn giản đi điều kiện dùng theo sơ đồ sau:
Procedure Try (i: integer);
Var j: integer;
Begin
if i > m then XUẤT else
For j:= 1 to n do if
Nhận được then:
Begin
Ghi nhận nó.
Try (i + 1);
Xóa bỏ việc ghi nhận; (quay lui}
end;
End;
- Thủ tục trên sẽ được khởi động bởi lệnh:
Try (1);
■ Ví dụ 1: (Bài toán 8 quân hậu)
Một bàn cờ quốc tế là một bảng hình vuông gồm có 8 hàng, 8 cột. Quân hậu là một quân cờ có thể ăn được bất kì quân nào nằm trên cùng một hàng, cùng một cột hay cùng một dường chéo. Bài toán đặt ra là: Hãy xếp 8 quân hậu trên bàn cờ sao cho không có quân hậu nào có thể ăn quân hậu nào. Điều đó cũng có nghĩa là trên mỗi hàng, mỗi cột, mỗi dường chéo chỉ có thể có một quân hậu.
Bài giải:
Program EIGHT_QƯEEN;
Var a: array [1..8] of integer;
b: array [2.. 16] of integer;
c: array [-7..7] of integer;
x: array [1..8] of integer;
i: integer;
procedure print;
var j: integer;
Begin
For j:= 1 to 8 do write (x[k] : 4);
Writein;
Readln;
end;
procedure Try (i: integer);
var j: integer;
Begin
if i > 8 then prim else
For j := 1 to 8 do
if (a[j] = 0) and (b[i + j] = 0) and (c[i – j] = 0) then
Begin
x[i] := j;
a[j] := 1; b[i + j]:= 1; c[i - j]:= 1
Try (+1);
a[j]:= 0; b[i + j]:= 0; c[i - j]:= 0
end;
end;
procedure Init;
var j: integer;
Begin
Fillchar (a, sizeof(a), 0);
Fillchar (b, sizeof(b), 0);
Fillchar (c, sizeof(c), 0);
end;
Begin
Init
Try (1);
end.
■ Ví dụ 2: (Bài toán Mã đi tuần)
Chu một bàn cờ kích thước n x n. Một con mã di chuyển theo luật cờ vua được đặt trong một ô với tọa độ đầu là (Xo, Yo). Hãy lập trình tim một đường đi với n2 - 1 bước đi sao cho mọi ô trên bàn cờ đều được mã nhảy đến đúng một lần.
Bài giải:
Program Knighttour;
Const
a: array [1..8] of integer = (2, 1, -1, -2, -2, -1, 1, 2);
b: array [1..8] of integer = (1, 2, 2, 1, -1, -2,-2, -1);
n = 5; nsq = 25;
Type
index = 1..n;
Var
q: Boolean;
dd: Array [index, index] of integer;
S: Set of index;
x, y: integer;
Procedure Init;
Begin
Fillchar (dd, size of (dd), 0);
Writein ('Xin cho biết tọa độ ban đầu của ngựa');
Readln (x, y);
dd[x, y] := 1;
q := False;
S := [1, 2, 3, 4, 5];
end;
procedure print;
Var i, j: integer;
Begin
q := True;
For j:= 1 to n do
Begin
For j := 1 to n do write (dd[i, j] : 5);
writeln;
end;
end;
procedure Try (i)
Var
j, u, v: integer;
If i > nsq then
print
Else For j := 1 to 8 do
Begin
u := x + a[j];
v := y + b[j];
if (u in s) and (v in s) and (dd[u, v] = 0)
then
Begin
dd[u, v] := i;
x := u; y := v;
Try(i + 1);
x := u - a[j];
y := v – b[j];
dd[u, v] := 0
end;
end;
end;
Begin
Init;
Try (2);
if q = False then writeln ('NO SOLUTION');
end;