Bài giảng về thuật đệ quy quay lui (Pascal).doc

Bài giảng chuyên đề về giải thuật đệ quy quay lui

Để hiểu được giải thuật đệ quy quay lui, trước hết ta nhắc lại khái niệm về đệ qui.

1. Đệ quy
1.1 Khái niệm về đệ qui.
Ta nói một khái niệm là đệ qui nếu nó gao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.
Ví dụ:
1. Số tự nhiên:
a./ 1 là số tự nhiên
b./ X là số tự nhiên nếu X - 1 là số tự nhiên..
2. Hàm n giai thừa ( n!)
a./ o! =1
b./ n!=n(n-1)! nếu n > 0

1.2 Giải thuật đệ quy và thủ tục đệ qui
Nếu lời giải của một bài toán T được thực hiện bằng lời giải của bài toán T` có dạng giống như T, thì đó là lời giải đệ qui.Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ qui.( T` ở đây hiểu theo nghĩa nó phải nhỏ hơn T)
Thủ tục đệ qui( chương trình con đệ qui) là thủ tục mà trong thủ tục đó có lời gọi tới chính thủ tục đó.

Đặc điểm của thủ tục đệ qui:
a./ Trong thủ tục đệ qui có lời gọi đến chính thủ tục đó.
b./ Mỗi lần gọi lại thủ tục đó thì kích thước bài toán đã thu nhỏ hơn trước.
c./ Có một trường hợp đặc biệt: đó là trường hợp suy biến.
Ví dụ:
1. Tính n!
n! =1.2.3...n

function gt(x:integer):longint;
begin
if x = 0 then
gt:=1
else
gt:=x*gt(x-1);
end;

2. Số FIBONACCI.
Dãy số a1, a2, a3 , ..., an... được gọi là dáy số fibonacci nếu a1=a2=1, còn từ số thứ 3 trở đi bằng tổng của 2 số đứng ngay trước nó.
Ta có thủ tục đệ quy sau:

function fibo(x: integer): longint;
var
f1,f2 : integer;
Begin
if x<=2 then
fibo:=1
else
fibo:=f(x-2)+ f(x-1);
end;

Cả hai thủ tục trên ta thấy rất rõ 3 đặc điểm trên của thủ tục đệ quy.
- Thủ tục có lời gọi đến chính thủ tục đó.
- Lần gọi sau kích thước bài toán nhỏ hơn( lần trước tính n!, nhưng lần sau chỉ tính (n-1)!)
- Có trường hợp suy biến( Nếu n=1; gt=1; nếu n ≤ 2 fibo =1).

1.3 Hiệu lực của đệ quy:
ưu điểm: Sáng sủa, dễ hiểu, thủ tục rất gọn, đơn giản
Nhược điểm: Tính toán nhiều, thời gian thực hiện rất lâu.

1.4 Ví dụ về giải thuật đệ qui trên lưới ô vuông.
Xét bài toán sau:
Cho lưới ô vuông cấp NxM. Trên mỗi ô [i,j] của lưới ghi một số nguyên a[i,j]. Hai ô được gọi là liên thông trực tiếp nếu nó chung cạnh và giá trị tuyệt đối của tổng 2 số ghi trên 2 ô đó là số chẵn. Hãy lập trình giải quyết các công việc sau:
a) Cho biết lưới ô vuông đó có bao nhiêu vùng liên thông( vùng liên thông gồm các ô liên thông trực tiếp hoặc liên