Kỹ thuật đệ qui

KYÕ THUAÄT ÑEÄ QUI
Kyõ thuaät laäp trình ñeä qui coù yù nghóa raát lôùn trong khoa hoïc maùy tính, coù raát
nhieàu thuaät toaùn ñoøi hoûi caøi ñaët raát phöùc taïp vaø caàu kyø neáu khoâng duøng kyõ thuaät
ñeä qui. Ñoái vôùi moät soá thuaät toaùn do baûn chaát töï nhieân cuûa chuùng ñaõ mang tính ñeä
qui, vieäc caøi ñaët ñeä qui laø goïn vaø ñeïp nhaát. Khuyeát ñieåm lôùn nhaát cuûa kyõ thuaät ñeä
qui laø: lôøi giaûi ñeä qui cho moät soá baøi toaùn coù theå bò chaïy raát chaäm do söï buøng noã toå
hôïp.
I.

KHAÙI NIEÄM VEÀ CHÖÔNG TRÌNH ÑEÄ QUI
Moät thuû tuïc (hay haøm) ñöôïc goïi laø coù tính ñeä qui neáu trong thaân cuûa thuû tuïc
(hay haøm) ñoù coù leänh goïi laïi chính noù moät caùch töôøng minh hay tieàm aån.
Ví duï 1. Vôùi n laø soá nguyeân khoâng aâm, ta ñònh nghóa n! nhö sau:
0!=1,
n!=n.(n-1)! neáu n≥1.
Haõy caøi ñaët chöông trình tính n!.
Ñaây laø moät ví duï coù theå caøi ñaët deã daøng baèng phöông phaùp thoâng thöôøng, tuy
nhieân neáu döïa vaøo ñònh nghóa cuûa n! chuùng ta coù theå caøi ñaët moät caùch töï nhieân
baèng phöông phaùp ñeä qui nhö sau.
long GiaiThua(int n) /* n >= 0 */
{
long ret;
/* gia tri traû veà cuûa haøm */
if(n==0)
/* ñieàu kieän kieän döøng */
ret = 1;
else
ret = n*GiaiThua(n-1); /* goïi laïi chính noù */
return ret;
}
Ñoái vôùi ví duï naày, caùch caøi ñaët baèng ñeä qui raát töï nhieân vaø ñôn giaûn nhöng
khoâng phaûi laø caùch caøi ñaët hay nhaát. Chuù yù raèng baát kyø haøm ñeä qui naøo cuõng phaûi
coù ñieàu kieän döøng, ñieàu kieän naày seõ keát thuùc quaù trình ñeä qui baèng moät ñoaïn maõ
chöông trình ñöôïc vieát theo loái thoâng thöôøng. Caâu leänh if(n==0)... trong ví duï treân
laø ñieàu kieän döøng cuûa haøm GiaiThua.
Ví duï 2. Haøm tính caên baäc 3 cuûa moät soá thöïc coù theå caøi ñaët ñeä qui theo hai haøm
exp vaø log (haøm logarithm ln(x)) nhôø vaøo nhaän xeùt sau ñaây:

x > 0 : 3 x = e ln ( x ) / 3
x = 0: 3 x = 0
x < 0: 3 x = − 3 − x .

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

14

#include
#include
double sqrt3(double x)
{
double ret;
if(x==0)
/* ñieàu kieän döøng */
ret = 0;
else
if(x=1 && x+strlen(ch)-1=1 && y
{
if(< ñieàu kieän döøng >)
{
/* Traû veà giaù trò hay keát thuùc coâng vieäc ...*/
}
else
{
/* Laøm moät soá coâng vieäc ... */
/* Goïi ñeä qui */
}
}
II.2 Ñeä qui nhò phaân
Caùc haøm ñeä qui nhò phaân coù daïng sau ñaây.
< Teân vaø danh saùch tham soá >
{
if(< ñieàu kieän döøng >)
{
/* Traû veà giaù trò hay keát thuùc coâng vieäc ... */
}
else
{
/* Laøm moät soá coâng vieäc ...*/
/* Goïi ñeä qui (1) ñeå giaûi quyeát vaán ñeà nhoû hôn */
/* Goïi ñeä qui (2) ñeå giaûi quyeát noát vaán ñeà coøn laïi */
}

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

16

}
Ñeä qui nhò phaân ñoùng vai troø raát quan troïng, chuùng ta thöôøng duøng phöông
phaùp naày ñeå caøi ñaët caùc thuaät toaùn "chia ñeå trò", thuaät toaùn duyeät caây nhò phaân...
Ví duï: Daõy Fibonaci {Fn} ñöôïc ñònh nghóa truy hoài nhö sau:
Fo=F1=1,
Fn=Fn-1 + Fn-2 neáu n ≥ 2.

Haøm ñeä qui nhò phaân sau ñaây seõ tính giaù trò cuûa Fn, giaù trò phaàn töû thöù n trong
daõy Fibonaci, baèng caøi ñaët ñeä qui, ñaây laø moät caøi ñaët töï nhieân vaø ñôn giaûn nhaát
nhöng cuõng laø caùch caøi ñaët chaïy chaäm nhaát.
long Fibo(int n)
{
long ret, Fn_1, Fn_2;
if(n