Tài liệu Kỹ thuật lập trình đệ qui

eõ toát 
hôn. Moät soá thuaät toaùn khaùc mang tính "chia ñeå trò" theo kieåu nhò phaân thì caøi ñaët 
ñeä qui nhò phaân seõ theå hieän roõ tính töï nhieân cuûa thuaät vaø coù thôøi gian chaïy khaù toát. 
Döôùi ñaây laø moät phieân baûn ñeä qui tuyeán tính ñeå tính phaàn töû thöù n cuûa daõy 
Fibonaci. 
void FiboLinear(int n, long* F_n_1, long* F_n) 
/* F_n_1: Fn-1; F_n: Fn; F_n_2: Fn-2 */ 
{ 
 long F_n_2; 
 if(n<=1) 
 { 
 *F_n_1 = 1; 
 *F_n = 1; 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 17
 } 
 else 
 { 
 FiboLinear(n-1, &F_n_2, &(*F_n_1) ); 
 *F_n = *F_n_1 + F_n_2; 
 } 
} 
II.3 Ñeä qui phi tuyeán 
Trong caùc chöông trình ñeä qui phi tuyeán, vieäc goïi ñeä qui seõ ñöôïc thöïc hieän beân 
trong voøng laëp, sau ñaây laø maãu chung cuûa moät haøm hay thuû tuïc ñeä qui phi tuyeán. 
; 
{ 
 for(i=1; i<=n; i++) 
 { 
 /* Laøm moät soá coâng vieäc ...*/ 
 if() 
 { 
 /* Laøm moät soá coâng vieäc ...*/ 
 } 
 else 
 /* Goïi ñeä qui */ 
 } 
} 
Ví du: Cho daõy {Xn} xaùc ñònh theo coâng thöùc truy hoài sau ñaây: 
Xo=1, 
Xn=n2Xo + (n-1)2X1 + ... + 12Xn-1 , neáu n ≥ 1. 
Nhö caùc ví duï tröôùc, chuùng ta coù theå tính daõy naày baèng phöông phaùp ñeä qui, 
bôûi vì baûn chaát ñöôïc ñònh nghóa ñeä qui cuûa daõy. Tröôøng hôïp naày vieäc goïi ñeä qui 
ñöôïc thöïc hieän trong voøng laëp. 
long Xn(int n) 
{ 
 int i; 
 long ret; /* gia tri tra ve */ 
 if(n==0) 
 ret=1; 
 else 
 { 
 ret = 0; 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 18
 for(i=0; i<n; i++) 
 ret = ret + (n-i)*(long)(n-i)*Xn(i); 
 } 
 return ret; 
} 
II.4 Ñeä qui hoã töông 
 Moät chöông trình ñeä qui hoã töông goïi laïi chính noù moät caùch giaùn tieáp thoâng 
qua chöông trình khaùc. Ví duï 3 beân treân laø moät ví duï veà ñeä qui hoã töông. Moät daïng 
ñeä qui hoã töông ñôn giaûn laø tröôøng hôïp hai haøm goïi qua laïi laãn nhau, daïng naày coù 
caáu truùc nhö sau: 
void Proc1(...) 
{ 
 /* laøm moät soá vieäc */ 
 Proc2(...) 
 /* laøm moät soá vieäc */ 
} 
void Proc2(...) 
{ 
 /* laøm moät soá vieäc */ 
 Proc1(...) 
 /* laøm moät soá vieäc */ 
} 
Ví duï: Xeùt hai daõy {Xn}, {Yn} ñöôïc ñònh nghóa nhö sau: 
Xo=Yo=0 
Xn = Xn-1 + Yn-1 
Yn = n2Xn-1+ Yn-1 
Hai daõy naày ñöôïc tính nhôø vaøo hai haøm TinhX vaø TinhY goïi hoã töông laãn nhau 
ñöôïc minh hoïa qua caøi ñaët döôùi ñaây. 
long TinhX(int n); 
long TinhY(int n); 
long TinhX(int n) 
{ 
 long ret; /* giaù trò traû veà */ 
 if(n<=0) 
 ret = 1; 
 else 
 ret = TinhX(n-1)+TinhY(n-1); 
 return ret; 
} 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 19
long TinhY(int n) 
{ 
 long ret; /* giaù trò traû veà */ 
 if(n<=0) 
 ret = 1; 
 else 
 ret = n*(long)n*TinhX(n-1)+TinhY(n-1); 
 return ret; 
} 
III. THEO DOÕI HOAÏT ÑOÄNG CUÛA CHÖÔNG TRÌNH ÑEÄ QUI 
Do coù caáu truùc ñaëc bieät, caùc chöông trình ñeä qui khaùc haún vôùi caùc chöông trình 
thoâng thöôøng. (Caùc chöông trình thoâng thöôøng chæ duøng caùc leänh tuaàn töï, caáu truùc 
reû nhaùnh, leänh nhaûy, hay caáu truùc laëp). Vì vaäy ngöôøi laëp trình raát khoù khaên trong 
vieäc theo doõi vaø kieåm tra caùc chöông trình ñeä qui, nhaát laø khi chöông trình coù loãi. 
Vôùi caùc coâng cuï baét loãi chöông trình hieän nay, ngöôøi laäp trình chæ theo doõi ñöôïc 
traïng thaùi hieän haønh trong moät laàn goïi ñeä qui chöù chöa hình dung ñöôïc toaøn boä 
traïng thaùi cuûa chöông trình (chaúng haïn nhö ñang goïi ñeä qui ôû taàng thöù maáy vaø 
ñang ôû laàn goïi naøo trong taàng naày, giaù trò cuûa caùc bieán cuïc boä ôû moãi laàn goïi laø bao 
nhieâu, giaù trò cuûa caùc tham soá ...). 
Trong phaàn naày chuùng ta seõ nghieân cöùu moät phöông phaùp theo doõi caùc 
chöông trình ñeä qui, phöông phaùp naày coù theå duøng keát hôïp chaët cheõ vôùi caùc coâng 
cuï baét loãi chöông trình. 
Moãi chöông trình ñeä qui seõ ñöôïc bieåu dieãn baèng moät caây, goác cuûa caây ñaïi dieän 
cho laàn goïi ñaàu tieân, caùc nuùt cuûa caây ñaïi dieän cho caùc laàn goïi ñeä qui, moãi nuùt löu 
giaù trò hieän taïi cuûa caùc bieán cuïc boä hay caùc tham soá trong moät laàn goïi ñeä qui, caùc 
nuùt laù öùng vôùi laàn goïi ñeä qui gaëp ñieàu kieän döøng. Tuøy theo loaïi ñeä qui maø caây coù 
caáu truùc ñaëc tröng, ví duï ñeä qui nhò phaân seõ ñöôïc bieåu dieãn baèng caây nhò phaân, ñeä 
qui tuyeán tính bieåu dieãn baèng moät caây suy thoaùi (thaønh moät xaâu ñôn). 
Ví du: Bieåu dieãn cuûa haøm ñeä qui Fibo trong phaàn treân vôùi n=5, ta kyù hieäu Fibo(n) 
laø Fn. Hình döôùi ñaây laø caây nhò phaân bieåu dieãn cuûa haøm Fibo. Chuùng ta cuõng 
nhaän thaáy coù nhieàu nuùt laëp laïi trong caây. Ñieàu naày chöùng toû cuøng moät giaù trò ñöôïc 
tính ñi, tính laïi nhieàu laàn. Ñieàu naày laøm cho chöông trình chaïy raát chaäm. 
 F5=F3+F4
F3=F1+F2 F4=F2+F3
F1=1 F2=F0+F1 
F1=1 F0=1
F2=F0+F1 F3=F1+F2
F1=1F0=1 F1=1 F2=F0+F1 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 20
IV. MOÄT SOÁ BAØI TOAÙN ÑEÄ QUI THOÂNG DUÏNG 
IV.1 Baøi toaùn Thaùp Haø noäi 
Coù ba choàng ñóa ñöôïc ñaùnh soá laø 1, 2, 3. Khôûi ñaàu choàng ñóa soá 1 coù n ñóa, 
ñöôïc xeáp sao cho ñóa lôùn hôn luoân naèm beân döôùi, vaø hai choàng ñóa kia chöa coù ñóa 
naøo. Haõy chuyeån heát caùc ñóa töø choàng soá 1 sang choàng soá 3, moãi laàn chæ chuyeån 1 
ñóa, ñöôïc pheùp duøng choàng soá 2 laøm trung gian, trong quaù trình chuyeån phaûi baûo 
ñaûm ñóa lôùn hôn luoân naèm beân döôùi. Hình veõ beân döôùi minh hoïa tröôøng hôïp n=3 
ñóa. 
Baøi toaùn Thaùp Haø noäi coù theå giaûi raát ñôn giaûn baèng phöông phaùp ñeä qui theo 
thuaät toaùn sau. 
Thuaät toaùn Thaùp haø noäi 
Choàng soá 1 Choàng soá 2 Choàng soá 3
Neáu soá ñóa n=1 thì hieån nhieân coù theå chuyeån theo yeâu caàu cuûa baøi toaùn. Neáu 
ngöôïc laïi: 
- Böôùc 1: Goïi ñeä qui ñeå chuyeån n-1 ñóa töø choàng thöù 1 sang choàng thöù 2 
(choàng thöù 3 laøm trung gian). 
- Böôùc 2: Chuyeån ñóa thöù n töø choàng 1 sang choàng 3. 
- Böôùc 3: Goïi ñeä qui ñeå chuyeån n-1 ñóa töø choàng thöù 2 sang choàng thöù 3 
(choàng thöù 1 laøm trung gian). 
Thuaät toaùn treân ñöôïc caøi ñaët ñeä qui baèng haøm Tower döôùi ñaây. Haøm naày goïi 
haøm MoveDisk ñeå chuyeån ñóa cuoái cuøng. Trong caøi ñaët naày haøm MoveDisk chæ 
nhaèm höôùng daãn trình töï chuyeån ñóa. Baèng caùch söûa haøm MoveDisk thích hôïp, 
chuùng ta coù theå giaû laäp quaù trình di chuyeån ñóa treân maøn hình cuûa maùy tính. 
#include 
void MoveDisk(int src, int des) 
{ 
 printf("Töø %d Ñeán %d\n", src, des); 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 21
} 
void Tower(int n, int col1, int col2, int col3) 
/*col1: xuaát phaùt; col2: trung gian; col3: ñeán*/ 
{ 
 if(n>0) 
 { 
 /* chuyeån n-1 ñóa töø col1 sang col2; col3 trung gian */ 
 Tower(n-1, col1, col3, col2); 
 MoveDisk(col1, col3); /* chuyeån ñóa cuoái */ 
 /* chuyeån n-1 ñóa töø col2 sang col3; col1 trung gian */ 
 Tower(n-1, col2, col1, col3); 
 } 
} 
Chuùng ta seõ minh hoïa hoaït ñoäng cuûa thuaät toaùn baèng caùch veõ caây bieåu dieãn 
cho thuaät toaùn vôùi n=3, thuaät toaùn treân thuoäc loaïi ñeä qui nhò phaân neân caây bieåu 
dieãn seõ laø moät caây nhò phaân. Caùc nuùt laù öùng vôùi caùc leänh goïi Tower(0,?,?,?) ñöôïc 
boû qua bôûi vì caùc leänh naày khoâng laøm gì caû. 
Tower(3,1,2,3)
Töø 1 Ñeán 3 
Tower(2,1,3,2) 
Töø 1 Ñeán 2 
Tower(2,2,1,3)
Töø 2 Ñeán 3 
Tower(1,1,2,3) 
Töø 1 Ñeán 3 
Tower(1,3,1,2)
Töø 3 Ñeán 2 
Tower(1,2,3,1)
Töø 2 Ñeán 1 
Tower(1,1,2,3) 
Töø 1 Ñeán 3 
Döïa vaøo hình veõ treân chuùng ta laäp ñöôïc baûng moâ taû traïng thaùi hoaït ñoäng cuûa 
thuaät toaùn vôùi n=3, caùc ñóa ñöôïc kyù hieäu laø a, b, c vôùi giaû söû a > b > c, caùc ñóa treân 
hình veõ töø döôùi leân treân seõ ñöôïc kyù hieäu töø traùi qua phaûi. 
Söï hoaït ñoäng cuûa thuaät toaùn 
 Coät 1 Coät 2 Coät 3 
Khôûi ñaàu a b c 
Töø 1 Ñeán 3 a b c 
Töø 1 Ñeán 2 a b c 
Töø 3 Ñeán 2 a b c 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 22
Töø 1 Ñeán 3 b c a 
Töø 2 Ñeán 1 c b a 
Töø 2 Ñeán 3 c a b 
Töø 1 Ñeán 3 a b c 
IV.2 Thuaät toaùn phaùt sinh chænh hôïp vaø hoaùn vò 
IV.2.1 Hoaùn vò vaø chænh hôïp 
Cho moät taäp hôïp n phaàn töû Ω={1, 2, ..., n}. Moät hoaùn vò cuûa Ω laø moät daõy a1 
a2 ... an, trong ñoù ai ∈ Ω vaø chuùng ñoâi moät khaùc nhau. Moät taäp hôïp n phaàn töû seõ 
coù taát caû n! hoaùn vò. 
Ví duï: 
- Neáu Ω={a,b,c} thì a b c vaø b a c laø hai hoaùn vò cuûa Ω. 
- Neáu Ω={1, 2, 3} thì coù taát caû 3!=1x2x3=6 hoaùn vò cuûa Ω laø 123, 132, 231, 213, 
312, 321. 
Cho moät taäp hôïp n phaàn töû Ω={1, 2, ..., n} vaø moät soá nguyeân k (1 ≤ k ≤ n). Moät 
chænh hôïp chaäp k cuûa Ω laø moät daõy μ coù k phaàn töû ñöôïc laáy ra töø Ω vaø caùc phaàn töû 
cuûa μ ñoâi moät khaùc nhau. 
Ví duï: 
Vôùi Ω={1, 2, 3} thì 1 2, 2 1, 1 3, 3 1, 2 3, 3 2 laø caùc chænh hôïp chaäp 2 cuûa Ω. 
Ta thaáy ngay moät chænh hôïp chaäp n cuûa moät taäp hôïp Ω (coù n phaàn töû) chính laø 
moät hoaùn vò cuûa Ω. Soá caùc chænh hôïp chaäp k cuûa n phaàn töû ñöôïc kyù hieäu laø: A , ta 
coù A , hôn nöõa A coù theå tính theo coâng thöùc sau ñaây. 
n
k
nn
n = ! nk
Soá löôïng caùc chænh hôïp chaäp k cuûa n phaàn töû ñöôïc xaùc ñònh theo coâng 
thöùc: 
A n
n kn
k = −
!
( )! 
Ví duï: 
Coù 4 ñôït söûa xe vaø 3 khaùch haøng teân Lan, Huøng, Chaâu. Caùc thoâng tin lieân quan 
ñöôïc cho trong hai baûng nhö sau: 
Ñôït 
söûa 
Thôøi 
ñieåm baét 
ñaàu 
 Khaùch 
haøng 
Thôøi 
gian 
söûa 
Thôøi ñieåm 
giao xe 
1 7:00 Lan 2,0 giôø 19:00 
2 9:30 Huøng 1,5 giôø 15:00 
3 12:00 Chaâu 2,0 giôø 10:30 
4 15:00 
Nghæ 18:00 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 23
Coù theå nhaän söûa ñeå ñaùp öùng yeâu caàu cho caû 3 khaùch haøng treân hay khoâng? 
Chuùng ta coù theå laäp baûng cho moãi tröôøng hôïp cuûa chænh hôïp chaäp 3 cuûa 4 
phaàn töû ñeå xeùt xem moãi tröôøng hôïp coù bao nhieâu khaùch haøng ñöôïc thoûa maõn. 
Khaùch 
haøng 
Phöông 
aùn 1 
Phöông 
aùn 2 
Phöông 
aùn 3 
... 
Lan 
Huøng 
Chaâu 
ñôït 1 
ñôït 2 
ñôït 3 
(treå) 
ñôït 1 
ñôït 3 
ñôït 2 (treå) 
ñôït 3 
ñôït 2 
ñôït 1 
IV.2.2 Thuaät toaùn phaùt sinh chænh hôïp 
Do hoaùn vò laø moät tröôøng hôïp ñaëc bieät cuûa chænh hôïp (khi k=n) neân chuùng ta 
chæ baøn ñeán thuaät toaùn phaùt sinh taát caû caùc chænh hôïp chaäp k cuûa n phaàn töû. Ñaây 
cuõng laø thuaät toaùn duyeät qua taát caû caùc chænh hôïp trong caùc baøi toaùn toå hôïp nhö ví 
duï treân. Thuaät toaùn coù moät tham soá i, khi goïi ñeä qui thì giaù trò tham soá naày thay ñoåi, 
khôûi ñaàu i nhaän giaù trò 1. 
- Goïi haøm: Phatsinh(a, n, k, 1) 
- Haøm ñeä qui Phatsinh(a, n, k, i) 
Laëp j=i ñeán n laøm 
 Ñoåi choã aj vaø ai 
 Neáu j<k thì 
 goïi ñeä qui Phatsinh(a, n, k, i+1) 
 Ngöôïc laïi 
 xöû lyù a1 a2 ... ak 
 Ñoåi choã aj vaø ai 
Cuoái laëp 
IV.3 Thuaät toaùn phaùt sinh toå hôïp 
IV.3.1 Toå hôïp 
Cho moät taäp hôïp n phaàn töû Ω={1, 2, ..., n} vaø moät soá nguyeân k (1 ≤ k ≤ n). Moät 
toå hôïp chaäp k cuûa Ω laø moät taäp con cuûa Ω coù k phaàn töû. 
Ví duïï: Vôùi Ω={1, 2, 3}, caùc toå hôïp chaäp 2 cuûa Ω laø {1,2}, {1,3}, {2,3}. 
Soá löôïng toå hôïp chaäp k cuûa n phaàn töû ñöôïc kyù hieäu laø C ñöôïc tính theo coâng 
thöùc sau ñaây. 
n
k
Soá löôïng caùc toå hôïp chaäp k cuûa n phaàn töû ñöôïc xaùc ñònh theo coâng 
thöùc: 
C n
k n kn
k = −
!
!( )! 
IV.3.2 Thuaät toaùn 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 24
Thuaät toaùn sau phaùt sinh taát caû caùc toå hôïp chaäp k cuûa taäp {1, 2, ..., n}. Töông 
töï thuaät toaùn phaùt sinh chænh hôïp, thuaät toaùn naày goïi ñeä qui vôùi tham soá i, khôûi ñaàu 
i=1 vaø ao=0. 
- Khôûi taïo ao=0 
- Goïi haøm Phatsinh(a, n, k, 1) 
- Haøm ñeä qui Phatsinh(a, n, k, i) 
ai=ai-1 
Trong khi ai < n-k+i laøm 
 ai=ai+1 
 Neáu i<k thì 
 goïi ñeä qui Phatsinh(a, n, k, i+1) 
 Ngöôïc laïi 
 xöû lyù {a1, a2, ..., ak} 
Cuoái laëp 
V. MOÄT SOÁ ÖÙNG DUÏNG KHAÙC 
Trong phaàn naày chuùng ta tìm lôøi giaûi ñeä qui cho moät soá baøi toaùn ñaõ ñöôïc giaûi 
trong caùc chöông khaùc maø khoâng caàn duøng kyõ thuaät ñeä qui. Moät soá lôøi giaûi ñöôïc 
trình baøy ôû ñaây maëc duø khoâng hieäu quaû veà maët thôøi gian chaïy nhöng raát ñôn giaûn 
vaø ñeïp. Khi kích thöôùc baøi toaùn khaù nhoû thì coù leû ñaây laø nhöõng thuaät toaùn khaù hay. 
Maët khaùc, caùc baøi giaûi naày cuõng laø minh hoïa cho caùch suy nghó vaø giaûi baøi toaùn 
moät caùch töï nhieân. 
V.1 Tính toång 
Vieäc tính toång n soá trong moät maûng moät chieàu (chaúng haïn nhö maûng goàm caùc 
soá nguyeân) coù theå giaûi quyeát deã daøng baèng thuaät toaùn ñeä qui nhö sau: 
- Neáu n<1 thì toång soá=0 
- Ngöôïc laïi thì laøm 
 Tính toång a[0] +  + a[n-2] baèng ñeä qui 
 Coäng giaù trò tính ñöôïc vôùi a[n-1]. 
Cuoái ngöôïc laïi 
Thuaät toaùn coù theå caøi baèng moät haøm ñeä qui nhö sau. 
long TongSo(int a[], int n) 
{ 
 if(n<1) 
 return 0; 
 else 
 return TongSo(a, n-1) + a[n-1]; 
} 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 25
V.2 Tìm phaàn töû lôùn nhaát, phaàn töû nhoû nhaát 
Thuaät toaùn ñeä qui sau ñaây tìm chæ soá cuûa phaàn töû lôùn nhaát trong caùc soá a[0], 
a[1], , a[n-1]. (Bieán csmax löu chæ soá caàn tìm.) Tröôøng hôïp tìm phaàn töû nhoû nhaát 
coù theå laøm hoaøn toaøn töông töï. 
- Neáu n<1 thì csmax=-1 (maûng khoâng coù phaàn töû); 
- Ngöôïc laïi neáu n=1 thì csmax=0; 
- Ngöôïc laïi neáu n>1 thì laøm 
 tính csmax baèng ñeä qui cho a[0], a[1], , a[n-2] 
 neáu a[csmax]<a[n-1] thì caäp nhaät csmax=n-1 
Cuoái ngöôïc laïi 
Sau ñaây laø caøi ñaët cho tröôøng hôïp tìm soá lôùn nhaát trong moät maûng caùc soá 
nguyeân. Haøm ChiSoMax traû veà moät chæ soá cuûa phaàn töû lôùn nhaát cuûa maûng. 
int ChiSoMax(int a[], int n) 
{ 
 int csmax; 
 if(n<1) 
 csmax=-1; 
 else if(n==1) 
 csmax = 0; 
 else 
 { 
 csmax = ChiSoMax(a, n-1); 
 if(a[csmax] < a[n-1]) 
 csmax = n-1; 
 } 
 return csmax; 
} 
V.3 Saép xeáp theo thöù töï taêng hay giaûm 
Chuùng ta trôû laïi baøi toaùn saép xeáp caùc soá trong moät maûng sao cho coù ñöôïc thöù 
töï taêng a[0]≤a[1] ≤  ≤ a[n-1]. Tröôøng hôïp caàn saép xeáp theo thöù töï giaûm thì coù theå 
giaûi quyeát hoaøn toaøn töông töï. 
V.3.1 Thuaät toaùn 1 
Vieäc saép xeáp n phaàn töû theo thöù töï taêng coù theå thöïc hieän ñeäqui nhö sau: 
Neáu n>1 thì 
 Saép xeáp a[0], a[1], , a[n-2] nhôø goïi ñeä qui 
 Neáu a[n-2]>a[n-1] thì { neáu a[n-2]≤a[n-1] thì ñaõ saép xong } 
 Ñoåi choã a[n-2] vaø a[n-1] 
 Saép xeáp a[0], a[1], , a[n-2] nhôø goïi ñeä qui 
 Cuoái neáu { a[n-2]>a[n-1] } 
Cuoái neáu { n>1} 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 26
Thuaät toaùn coù theå ñöôïc caøi ñaët baèng haøm ñeä qui SapXep nhö sau. 
void SapXep(int a[], int n) 
{ 
 int x; 
 if(n>1) 
 { 
 SapXep(a, n-1); 
 if(a[n-2]>a[n-1]) 
 { 
 x = a[n-2]; 
 a[n-2] = a[n-1]; 
 a[n-1] = x; 
 SapXep(a, n-1); 
 } 
 } 
} 
V.3.2 Thuaät toaùn 2 
Thuaät toaùn ñeä qui sau ñaây saép xeáp taêng döïa vaøo haøm ChiSoMax. Haøm naày traû 
veà chæ soá trong maûng cuûa phaàn töû lôùn nhaát cuûa maûng; haøm naày cuõng coù theå caøi 
ñaët ñeä qui nhö trình baøy beân treân. 
Neáu n>1 thì 
 Tìm csmax=ChiSoMax(a, n-1) 
 { chæ soá cuûa phaàn töû lôùn nhaát trong caùc ptöû a[0], , a[n-2] } 
 Neáu a[csmax]>a[n-1] thì 
 Ñoåi choã a[csmax] vaø a[n-1] 
 Cuoái neáu 
 Saép xeáp a[0], , a[n-2] nhôø goïi ñeä qui 
Cuoái neáu { n>1 } 
Thuaät toaùn coù theå ñöôïc caøi ñaët baèng haøm ñeä qui SapXep_1 nhö sau. 
void SapXep_1(int a[], int n) 
{ 
 int x, csmax; 
 if(n>1) 
 { 
 csmax = ChiSoMax(a, n-1); 
 if(a[csmax]>a[n-1]) 
 { 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 27
 x = a[csmax]; 
 a[csmax] = a[n-1]; 
 a[n-1] = x; 
 } 
 SapXep_1(a, n-1); 
 } 
} 
V.4 Ñeám caùc phaàn töû phaân bieät 
Phaàn naày trình baøy caùch giaûi ñeä qui ñeå ñeám caùc phaàn töû phaân bieät trong maûng, 
caùc phaàn töû truøng nhau chæ ñeám moät laàn. Ví duï neáu maûng goàm 11 phaàn töû 19, 7, 7, 
21, 23, -23, -21, -19, 1, 1, 7 thì keát quaû ñeám laø 8. 
V.4.1 Thuaät toaùn 1 
Thuaät toaùn ñeä qui sau ñaây duøng moät haøm xaùc ñònh xem phaàn töû x coù naèm 
trong maûng a hay khoâng: 
int XuatHienTrong(int a[], int n, int x). 
Thuaät toaùn goàm caùc böôùc sau: 
Neáu n<0 thì keát quaû ñeám = 0 
Neáu n=1 thì keát quaû ñeám = 1 
Neáu n>1 thì 
 Goïi ñeä qui: kq1=Soá phaàn töû phaân bieät trong a[0], , a[n-2] 
 Neáu a[n-1] xuaát hieän trong a[0], , a[n-2] thì 
 keát quaû ñeám = kq1 
 Ngöôïc laïi 
 keát quaû ñeám = kq1+1 
Cuoái neáu 
Thuaät toaùn coù theå ñöôïc caøi ñaët baèng haøm ñeä qui DemPhanBiet nhö sau. 
int XuatHienTrong(int a[], int n, int x) 
{ 
 int i=0; 
 while(i<n && x!=a[i]) 
 i++; 
 return (i<n); 
} 
int DemPhanBiet(int a[], int n) 
{ 
 int ketqua, kq1; 
 if(n<1) 
 ketqua = 0; 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 28
 else if(n==1) 
 ketqua = 1; 
 else 
 { 
 kq1 = DemPhanBiet(a, n-1); 
 if(XuatHienTrong(a, n-1, a[n-1])) 
 ketqua = kq1; 
 else 
 ketqua = kq1+1; 
 } 
 return ketqua; 
} 
V.4.2 Thuaät toaùn 2 
Thuaät toaùn treân ñaõ duøng theâm moät haøm tìm kieám ñeå bieát a[n] coù xuaát hieän 
trong a[1], a[2], , a[n-1] hay khoâng. Sau ñaây laø moät caùch giaûi “thuaàn tuùy ñeä qui”. 
Tuy nhieân vieäc goïi ñeä qui coù theå bò thöïc hieän nhieàu laàn hôn. 
Neáu n<0 thì keát quaû ñeám = 0 
Neáu n=1 thì keát quaû ñeám = 1 
Neáu n>1 thì 
 Goïi ñeä qui: kq1=Soá phaàn töû phaân bieät trong a[0], , a[n-2] 
 Neáu a[n-1]=a[n-2] thì keát quaû ñeám = kq1 
 Ngöôïc laïi { a[n-1]≠ a[n-2] } 
 Goïi ñeä qui: kq2=Soá phaàn töû phaân bieät trong a[0], , a[n-3] 
 Goïi ñeä qui: kq3=Soá phaàn töû phaân bieät trong a[0], , a[n-3], a[n-1] 
 Neáu kq2=kq3 thì keát quaû ñeám = kq1 
 ngöôïc laïi keát quaû ñeám = kq1+1 
 Cuoái ngöôïc laïi { a[n-1]≠ a[n-2] } 
Cuoái neáu 
Thuaät toaùn coù theå ñöôïc caøi ñaët baèng haøm ñeä qui DemPhanBiet_1 nhö sau. Haøm 
traû veà keát quaû ñeám. Vieäc ñeám soá phaàn töû phaân bieät trong n-1 phaàn töû a[0], , a[n-
3], a[n-1] vaãn duøng maûng a: giaù trò a[n-2] ñöôïc ghi nhôù vaøo bieán x (gaùn x=a[n-2]), 
thay taïm a[n-2] bôûi a[n-1] (gaùn a[n-2]=a[n-1]), goïi ñeä qui haøm ñeám kq3 := 
DemPhanBiet_1(a, n-1), sau ñoù traû laïi giaù trò cuõ cho a[n-2] (gaùn a[n-2]=x). 
int DemPhanBiet_1(int a[], int n) 
{ 
 int ketqua, kq1, kq2, kq3; int x; 
 if(n<1) 
 ketqua = 0; 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 29
 else if(n==1) 
 ketqua = 1; 
 else /* n >= 2; a[n-2], a[n-1] hop le */ 
 { 
 kq1 = DemPhanBiet_1(a, n-1); 
 if(a[n-1]==a[n-2]) 
 ketqua = kq1; 
 else 
 { 
 kq2 = DemPhanBiet_1(a, n-2); 
 /* Ñeám a[1], ..., a[n-3], a[n-1]; taïm thay a[n-2]=a[n-1] */ 
 x = a[n-2]; 
 a[n-2] = a[n-1]; 
 kq3 = DemPhanBiet_1(a, n-1); 
 a[n-2] = x; /* traû laïi giaù trò cuõ cho a[n-2] */ 
 if(kq2==kq3) 
 ketqua = kq1; 
 else 
 ketqua = kq1+1; 
 } 
 } 
 return ketqua; 
} 
V.5 Tính luõy thöøa nhanh 
Vieäc tính luõy thöøa baäc n (n nguyeân) coù theå tính nhanh baèng caùch traùnh vieäc 
tính laïi caùc pheùp toaùn. Ví duï ñeå tính x14, vì x14=(x7)*(x7) neân chæ caàn tính x7 moät laàn; 
cuõng töông töï vì x7=(x3)*(x3)*x neân chæ caàn tính x3 moät laàn,  Haøm LuyThua ñeä qui 
sau ñaây caøi ñaët thuaät toaùn naày. 
float LuyThua(float x, int n) 
{ 
 float ret, xlast; 
 if(n<0) 
 ret = 1/LuyThua(x, -n); 
 else if(n==0) 
 ret = 1; 
 else if(n==1) 
 ret = x; 
 else /* n > 1 */ 
 { 
 if(n%2==0) 
Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM 30
 { 
 xlast = LuyThua(x, n/2); 
 ret = xlast*xlast; 
 } 
 else 
 { 
 xlast = LuyThua(x, (n-1)/2); 
 ret = xlast*xlast*x; 
 } 
 } 
 return ret; 
}