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;

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

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