Tìm hiểu về đệ quy
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (94.28 KB, 3 trang )
Giải thuật đệ quy
Võ Công Chương
Trong lập trình, đệ quy là một kĩ thuật khá tốt để giải quyết các vấn đề một cách ngắn gọn
và dễ hiểu. Chính vì thế, đệ quy đã được thường xuyên nhắc đến trong các số báo trước.
Trong bài viết này, tôi xin nêu ra một số bài toán đệ quy đơn giản. Với các bạn học sinh
chưa từng tìm hiểu về kĩ thuật này, tôi hy vọng bài viết sẽ giúp các bạn tiếp cận nó nhanh
chóng hơn.
A. Định nghĩa đệ quy
1. ý tưởng:
Để định nghĩa cái chưa biết, thường thường, người ta phải dùng những cái đã biết (đã có
định nghĩa) để định nghĩa cho cái chưa biết ấy.
Có một cách định nghĩa khác gọi là định nghĩa đệ quy: Để định nghĩa cái chưa biết (ở quy
mô, mức độ lớn hơn) ta dùng định nghĩa của chính nó (nhưng ở quy mô, cấp độ nhỏ hơn)
để định nghĩa về nó.
2. Các ví dụ:
a) Định nghĩa một số tự nhiên N. N là số tự nhiên nếu N là số thỏa mãn điều kiện sau:
- N=0 hoặc
- N>0 và N-1 là số tự nhiên;
b) Định nghĩa giai thừa của một số tự nhiên N, kí hiệu N!:
- Nếu N=0 thì N!=1;
- Nếu N>0 thì N!=N*(N-1)!; (dấu * là phép nhân)
c) Định nghĩa một số tự nhiên N là bội số của 5. N là bội số của 5 nếu N thỏa mãn điều
kiện sau:
- N=5 hoặc
- N>5 và N-5 là bội số của 5;
d) Định nghĩa tổng số đo các góc của một đa giác có N cạnh, kí hiệu SN:
- Nếu N=3 thì SN=180; (Đây là tổng số đo 3 góc của một tam giác)
- Nếu N >3 thì SN=SN
-1
+ S
3;
e) Định nghĩa tổng của N số tự nhiên liên tiếp từ 1 đến N, kí hiệu SN:
- Nếu N=1 thì SN=1;
- Nếu N>1 thì SN=SN
-1
+ N;
3. Nhận xét:
Một định nghĩa đệ quy thường phải có 2 ý:
- ý thứ nhất: Trường hợp cơ bản (trường hợp suy biến), là trường hợp hiển nhiên, là qui
ước và đồng thời nó là cơ sở để định nghĩa cho trường hợp không cơ bản.
- ý thứ hai: Trường hợp không cơ bản, định nghĩa nó bằng chính nó nhưng ở cấp nhỏ hơn.
B. Giải thuật đệ quy:
1. Định nghĩa:
Giải thuật A được gọi là giải thuật đệ quy nếu trong các bước của A có ít nhất một bước
gọi lại chính A một khi thỏa mãn điều kiện nào đó (nếu có).
Ví dụ:
Giải_thuật A (Các tham số);
Begin
…
Nếu (điều kiện là đúng) thì Gọi A (Các tham số)
Ngược lại, (Công việc cho trường hợp suy biến);
…
End;
2. Nhận xét:
Bài toán giải được bằng giải thuật đệ quy nếu nó có thể được định nghĩa một cách đệ quy.
Một giải thuật đệ quy không thể lúc nào cũng gọi lại chính nó mà phải dừng lại trong một
hoặc một số trường hợp nào đó (gọi là trường hợp suy biến), nếu không thì nó sẽ không có
tính dừng.
3. Các ví dụ (viết bằng NNLT Pascal):
a) Hàm tính giai thừa của số tự nhiên N:
Hàm sau không tính được giai thừa của N, vì không có trường hợp để dừng việc gọi đệ
quy:
Function Giaithua (N:byte):LongInt;
Begin
Giaithua:=N*Giaithua (N-1);
End;
Hàm sau mới tính được giai thừa của N:
Function Giaithua (N:byte):LongInt;
Begin
IF (N=0) Then Giaithua:=1
ELSE Giaithua:=N*Giaithua (N-1);
End;
b) Hàm tính giá trị phần tử thứ N (N≥0) của dãy FIBONACCI, kí hiệu FN:
Định nghĩa FN:
- Nếu N=0 hoặc N=1 thì FN=1;
- Nếu N>1 thì FN=FN
-1
+ FN
- 2
;
Cài đặt:
Function F(N:Byte):Integer;
Begin
If (N=1)OR (N=0) Then F:=1
Else F:=F(N-1)+F(N-2);
End;
c) Hàm tính giá trị của tổng sau theo N, kí hiệu Sn, với x cho trước:
Sn = xcosx + x
2
cos
2
x + …+ xncosnx
Định nghĩa Sn:
- Nếu n=1 thì Sn=xcosx;
- Nếu n>1 thì Sn=xcosx(1 + (xcosx + x
2
cos
2
x + …+ xn
-1
cosn
-1
x)) = xcosx(1 + S
(n-1)
);
Cài đặt:
Function S(n:Byte):Real;
Begin
If (n=1) Then S:=xcosx
Else S:=xcosx(1+S(n-1));
End;
d) Hàm tính ước số chung lớn nhất của hai số tự nhiên a và b, kí hiệu UCLN(a,b), cho a≥b.
Định nghĩa UCLN(a,b), a≥b: - Nếu b=0 thì UCLN(a,b)=a;
- Nếu b>0 thì UCLN(a,b)=UCLN(b,a mod b); {Cải tiến của giải thuật Euclid}
Cài đặt:
Function USCLN(a,b:Word):Word;
Begin
If (b=0) Then UCLN:=a
Else UCLN:=UCLN(b,a mod b);
End;
e) Hàm tìm xâu ngược, kí hiệu XNn, của một xâu có n kí tự (n≥0), kí hiệu Xn:
Ví dụ: Cho Xn=’ABCDE’ thì XNn=’EDCBA’.
Định nghĩa XNn:
- Nếu n=0 thì XNn=’’;
- Nếu n>0 thì XNn=X[n]+XNn
-1
;
Trong đó, X[n] là kí tự thứ n trong xâu X; Dấu + là phép toán nối xâu. Ví dụ:
’A’+’B’=’AB’.
Cài đặt:
Function XN(X:String;n:Byte):String; {xâu X có n kí tự}
Begin
If (n=0) Then XN:=’’
Else XN:=X[n]+XN(X,n-1);
End;
f) Hàm tính tổng các chữ số của một số tự nhiên An có n chữ số, kí hiệu tổng là S
An
:
Ví dụ: Cho số An = 12345 thì S
An
=15 vì 5+4+3+2+1=15.
Định S
An
:
- Nếu A
n
≤ 9 thì S
An
=An;
- Nếu An >9 thì S
An
=DV(An) + S
An-1
Trong đó, DV(An) cho ta chữ số hàng đơn vị của A
n
(tức DV(An) = A
n
mod 10); là tổng
các chữ số của A
n-1
, A
n-1
là số An đã bị cắt bỏ hàng đơn vị (tức A
n-1
=A
n
div 10).
Cài đặt:
Function S(A:Word):Word;
Begin
If (A<=9) Then S:=A;
Else So:=(A mod 10)+S(A div 10);
End;
Các bạn tiếp tục cài đặt cho các ví dụ đã đưa ra trong mục (A.2).
