§Ö quy vμ c¸c ph−¬ng ph¸p
khö ®Ö quy
PGS. TS. Ph¹m v¨n Êt
Khoa C«ng nghÖ th«ng tin - Tr−êng §H GTVT
Tãm t¾t: §Ö quy lμ c«ng cô m¹nh trong tin häc ®Ó lËp tr×nh c¸c bμi to¸n khã. Tuy nhiªn
c¸c hμm ®Ö quy th−êng ®ßi hái bé nhí lín, v× vËy vÊn ®Ò khö ®Ö quy lμ rÊt cÇn thiÕt. Trong b¸o
c¸o nμy tr×nh bÇy cÊu tróc, nguyªn lý ho¹t ®éng cña hμm ®Ö quy vμ c¸ch x©y dùng mét hμm
kh«ng ®Ö quy t−¬ng øng. So víi c¸c ph−¬ng ph¸p khö ®Ö quy ®· biÕt, th× m« h×nh tr×nh bÇy ë
®©y ®¬n gi¶n vμ dÔ dμng ¸p dông h¬n.
Summary: The recursive is a powerfull tool for programming difficult problems. However
the recursion functions offen demand a larger memory, so the recursive removal is very
neccessary. In this paper, we will present the structure and the activity of recursion functions
and a method of creating a corresponding non recursion function. This method is simpler and
easier to apply compared with known methods.
i. CÊu tróc cña hμm ®Ö quy
Hµm ®Ö quy gåm 2 phÇn:
+ PhÇn suy biÕn gåm mét dÉy c¸c c©u
lÖnh vµ kh«ng chøa c¸c lêi gäi ®Ö quy.
+ PhÇn tæng qu¸t còng bao gåm nhiÒu
c©u lÖnh, nh−ng bao gåm mét hoÆc nhiÒu lêi
gäi ®Ö quy (gäi tíi chÝnh hµm ®ang xÐt).
D−íi ®©y, sÏ gäi c¸c c©u lÖnh kh«ng
chøa lêi gäi ®Ö quy lµ c¸c phÐp to¸n c¬ b¶n.
VÝ dô xÐt hµm sau:
void P(x) // x nguyªn d−¬ng
{
if(x==1) // Suy biÕn - kh«ng cã lêi gäi ®Ö
quy
// chØ gåm c¸c phÐp to¸n c¬ b¶n
{
in 8 // phÐp to¸n c¬ b¶n
}
else // Tæng qu¸t, sÏ cã c¸c lêi gäi ®Ö quy
{
in x2 // phÐp to¸n c¬ b¶n
P(x-1) // Lêi gäi §Q thø 1
in x // phÐp to¸n c¬ b¶n
P(x-1) // Lêi gäi §Q cuèi
in 1 // phÐp to¸n c¬ b¶n
}
}
ii. Nguyªn lý ho¹t ®éng
2.1. Tr−íc khi b¾t ®Çu ch−¬ng trinh
§Æt mét dÊu hiÖu ®Æc biÖt vµo ng¨n xÕp
(vÝ dô k = 0) lµm dÊu hiÖu kÕt thóc hµm
2.2. C¸ch xö lý lêi gäi ®Ö quy
2.2.1. §Æt gi¸ trÞ hiÖn t¹i cña ®èi vµo
ng¨n xÕp (®Ó sau nµy lÊy ra dïng).
2.2.2. §Æt mét dÊu hiÖu vµo ng¨n xÕp (®Ó
sau nµy biÕt lèi trë vÒ - trë vÒ sau lêi gäi ®Ö
quy nµo).
2.2.3. C¨n cø vµo tham sè lêi gäi ®Ö quy
®Ó thay ®æi gi¸ trÞ cña ®èi.
2.2.4. NhÈy (trë vÒ) ®Çu hµm.
2.3. PhÇn suy biÕn - trë vÒ
2.3.1. Xö lý c¸c phÐp to¸n c¬ b¶n.
2.3.2. LÊy gi¸ trÞ cña ®èi (x) vµ dÊu hiÖu
(k) tõ ®Ønh ng¨n xÐp.
2.3.3. NhÈy tíi ®o¹n ch−¬ng tr×nh xö lý
trë vÒ (xem 2.4).
2.4. PhÇn tæng qu¸t - sÏ gÆp c¸c lêi
gäi ®Ö quy
2.4.1. Xö lý c¸c phÐp to¸n c¬ b¶n.
2.4.2. Xö lý lêi gäi ®Ö quy ®Çu tiªn gÆp
ph¶i.
2.5. §o¹n ch−¬ng tr×nh xö lý trë vÒ
2.5.1. Dùa vµo gi¸ trÞ cña k ®Ó ph©n biÖt
3 tr−êng hîp.
a. KÕt thóc hµm (k=0)
b. Trë vÒ tõ lêi gäi ®Ö quy i (k=i < m)
c. Trë vÒ tõ lêi gäi cuèi (k=m)
2.5.2. CÊu tróc cña ®o¹n ch−¬ng tr×nh
nh− sau:
if(k==0)
KÕt thóc hµm
else if(k==1)
{
1. C¸c c©u lÖnh sau lêi gäi §Q 1
2. Xö lý lêi gäi §Q 2
}
else if(k==2)
{
1. C¸c c©u lÖnh sau lêi gäi §Q 2
2. Xö lý lêi gäi §Q 3
}
....
else if(k==m) // trá vÒ tõ lêi gäi cuèi
{
1. C¸c c©u lÖnh sau lêi gäi §Q m
2. LÊy gi¸ trÞ cña ®èi (x) vµ dÊu
hiÖu (k) tõ ®Ønh ng¨n xÐp
3. NhÈy tíi ®o¹n ch−¬ng tr×nh xö
lý trë vÒ (Goto 2.4.2)
}
iii. tæ chøc hμm kh«ng ®Ö quy
3.1. Hç trî
CÇn t¹o mét ng¨n xÕp vµ x©y dùng c¸c
phÐp to¸n:
a. push(x,k) ®Ó ®−a ®èi x vµ dÊu hiÖu k
lªn ng¨n xÕp.
b. pop(x,k) ®Ó lÊy ®èi x vµ dÊu hiÖu k
tõ ®Ønh ng¨n xÕp.
3.2. CÊu tróc cña hµm kh«ng ®Ö quy
(dïng goto) gåm 4 phÇn
PhÇn 1. Khëi ®Çu.
Push(0,0) // §−a dÊu hiÖu ®Æc biÖt lªn
ng¨n xÕp lµm dÊu hiÖu kÕt thóc hµm
PhÇn 2. PhÇn tæng qu¸t (®Æt nh·n lµ
§ÇuHµm).
a. Xö lý c¸c phÐp to¸n c¬ b¶n
b. Khi gÆp lêi gäi §Q ®Çu tiªn th×:
+ Push(x,1)
+ Thay ®æi x
+ ChuyÓn ®Õn PhÇn 2 (goto §ÇuHµm)
PhÇn 3. PhÇn suy biÕn.
a. Xö lý c¸c phÐp to¸n c¬ b¶n.
b. LÊy gi¸ trÞ cña ®èi (x) vµ dÊu hiÖu (k) tõ
®Ønh ng¨n xÐp.
c. ChuyÓn ®Õn PhÇn 4 (goto TrëVÒ) //
Cã thÓ bá lÖnh nµy.
PhÇn 4. Xö lý trë vÒ (®Æt nh·n lµ TrëVÒ)
a. NÕu k=0 - kÕt thóc hµm.
b. NÕu 0 < k < m (trë vÒ tõ lêi gäi §Q
thø k).
+ Xö lý c¸c phÐp to¸n c¬ b¶n sau lêi
gäi §Q k.
+ Push(x,k+1).
+ Thay ®æi x.
+ ChuyÓn ®Õn PhÇn 2 (goto §ÇuHµm)
c. NÕu k = m (trë vÒ tõ lêi gäi §Q cuèi).
+ Xö lý c¸c phÐp to¸n c¬ b¶n sau lêi
gäi §Q m.
+ LÊy gi¸ trÞ cña ®èi (x) vµ dÊu hiÖu
(k) tõ ®Ønh ng¨n xÐp.
+ ChuyÓn ®Õn phÇn 4 (Goto TrëVÒ).
iv. VÝ dô
Dùa theo c¸c chØ dÉn cña môc 3, dÔ
dµng x©y dùng hµm kh«ng ®Ö quy t−¬ng øng
víi hµm ®Ö quy P(n) (xem môc 1) nh− sau:
// X©y dùng ng¨n xÕp
int s[100], top=0;
void push(int x, int k)
{
s[top++] = x ; s[top++] = k;
}
void pop(int &x, int &k)
{
k= s[--top] ; x= s[--top];
}
// Hµm kh«ng ®Ö quy
void P(int x)
{
int k;
push(0,0);
DauHam:
if(x>1)
{
// Tæng qu¸t
cout << x*x << "\n";
push(x,1);
x = x-1;
goto DauHam;
}
// x=1 - Suy biÕn
cout << x << "\n";
pop(x,k);
TroVe:
if(k==0) return;
else if(k==1)
{
cout << x << "\n";
push(x,2);
x = x-1;
goto DauHam;
}
else if(k==2) // cuoi
{
cout << 1 << "\n";
pop(x,k);
goto TroVe;
}
}
v. M« h×nh khö ®Ö quy tæng qu¸t
dïng goto
Dùa trªn c¸c ý t−ëng cña c¸c môc 3 vµ 4,
cã thÓ ph¸t biÓu c¸ch khö ®Ö quy tæng qu¸t
nh− sau.
5.1. Hµm ®Ö quy tæng qu¸t cã thÓ diÔn
®¹t nh− sau
P(x) : if (S(x)) // suy biÕn
C(x)
else // tæng qu¸t
{
A1(x); P(f1(x)); // Gäi §Q 1
A2(x); P(f2(x)); // Gäi §Q 2
...
Am(x); P(fm(x)); // Gäi §Q m
Am+1(x);
}
5.2. Hµm kh«ng ®Ö quy t−¬ng øng
P(x):
int k; //khai b¸o biÕn k
push(0,0) ; // dÊu hiÖu kÕt thóc
DauHam:
if (!S(x) // kh«ng suy biÕn - tæng qu¸t
{
A1(x);
push(x,1);x=f1(x); goto DauHam;
}
//suy biÕn
C(x);
pop(x,k);
TroVe:
if(k==0) return ;
else if(k==1) // trë vÒ tõ lêi gäi §Q 1
{
A2(x);
push(x,2);x=f2(x); goto DauHam;
}
...
else if(k==m-1) // trë vÒ tõ lêi gäi §Q
m -1
{
Am(x);
push(x,m);x=fm(x); goto DauHam;
}
else if(k==m) // trë vÒ tõ lêi gäi §Q
cuèi
{
Am+1(x);
pop(x,k); goto TroVe;
}
vi. M« h×nh khö ®Ö quy tæng qu¸t
dïng while
Cã thÓ thay c¸c c©u lÖnh goto vµ c¸c
nh·n trong m« h×nh ë môc 5, b»ng c¸ch dïng
while vµ break (theo phong c¸ch C/C++) nh−
sau:
P(x):
int k; //khai b¸o biÕn k
push(0,0) ; // dÊu hiÖu kÕt thóc
while(1)
{
while(!S(x)) // S(x) sai - tæng qu¸t
{
A1(x);
push(x,1);x=f1(x);
}
// S(x) ®óng - suy biÕn
C(x);
pop(x,k);
while(1)
{
if(k==0) return ;
else if(k==1) // trë vÒ tõ lêi gäi §Q 1
{
A2(x);
push(x,2);x=f2(x); break;
}
...
else if(k==m-1) // trë vÒ tõ lêi gäi
§Q m -1
{
Am(x);
push(x,m);x=fm(x); break ;
}
else if(k==m) // trë vÒ tõ lêi gäi §Q cuèi
{
Am+1(x);
pop(x,k);
}
}
}
VÝ dô: NÕu theo m« h×nh trªn, th× hµm
trong môc 4 sÏ nh− sau:
void P(int x)
{
int k;
push(0,0);
while(1)
{
while(x>1)
{
//Tæng qu¸t
cout << x*x << "\n";
push(x,1);
x = x-1;
}
// Suy biÕn
cout << x << "\n";
pop(x,k);
while(1)
{
if(k==0) return; // kÕt thóc
hµm
else if(k==1) // trë vÒ tõ lêi
gäi §Q cuèi
{
cout << x << "\n";
push(x,2);
x = x-1;
break;
}
else if(k==2) // trë vÒ tõ lêi
gäi §Q cuèi
{
cout << 1 << "\n";
pop(x,k);
}
}
}
}
Tµi liÖu tham kh¶o
[1]. §ç Xu©n L«i. CÊu tróc d÷ liÖu vµ gi¶i thuËt.
NXB Gi¸o dôc, 1993.
[2]. Robert Sedgewick. CÈm nang thuËt to¸n (b¶n
dÞch). NXB Khoa häc vµ Kü thuËt, Hµ Néi, 1994.
[3]. Ph¹m V¨n Êt. Kü thuËt lËp tr×nh C c¬ së vµ
n©ng cao. NXB Khoa häc vµ Kü thuËt, Hµ Néi,
1999.
[4]. Ph¹m V¨n Êt. C++ vµ lËp tr×nh h−íng ®èi
t−îng. NXB Khoa häc vµ Kü thuËt, Hµ Néi, 2000¡