Bài giảng Kỹ thuật lập trình nâng cao - Chương 7: Lập trình đệ quy - Trần Minh Thái

Trần Minh Thái
minhthai@itc.edu.vn
*
1
*
*Môṭ ham̀ được goị co ́ tińh đệqui nêú trong
thân cuả ham̀ đo ́co ́lêṇh goị laị chińh no ́môṭ 
caćh tường minh hay tiêm̀ ân̉.
*Phân loaị đệqui
*Đệ qui tuyêń tińh.
*Đệqui nhịphân.
*Đệqui phi tuyêń.
*Đệqui hô t̃ương.
2
*
•Trong thân ham̀ có duy nhât́ môṭ lời goị ham̀ goị laị
chińh nómôṭ caćh tường minh.
 TenHam (́)
{
if (điêù kiêṇ dừng)
{
. . .
//Trảvềgia ́trịhay kêt́ thuć công viêc̣
}
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
. . . TenHam (́);
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
}
3
Vi ́du:̣ Tińh
- Điêù kiêṇ dừng: S(0) = 0.
- Qui tăć (công thức) tińh: S(n) = S(n-1) + n.
int TongS (int n)
{
if(n==0)
return 0;
return ( TongS(n-1) + n );
}
nnS ++++= L321)(
4
*
1. Tính n!
2. In ra các ước số của số nguyên dương
3. Đếm số lượng ước số của số nguyên dương
4. Tìm ước số chung lớn nhất của 2 số nguyên
dương
5. Kiểm tra số nguyên dương n có phải là số nguyên
tố?
6. Nhập vào mảng 1 chiều số nguyên a, kích thước n
7. Xuất mảng 1 chiều số nguyên a, kích thước n
8. Tìm phần tử có giá trị x trong mảng số nguyên a,
kích thước n
5
*
Trong thân cuả ham̀ cóhai lời goị ham̀ goị laị chińh nómôṭ caćh tường
minh.
 TenHam (́)
{
if (điêù kiêṇ dừng)
{
. . .
//Trảvềgia ́trịhay kêt́ thuć công viêc̣
}
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
. . .TenHam (́); //Giaỉ quyêt́ vâń đềnhỏhơn
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
. . . TenHam (́); //Giaỉ quyêt́ vâń đềcoǹ laị
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
} 6
Vi ́du:̣ Tińh sốhaṇg thứn cuả daỹ Fibonaci
được điṇh nghiã như sau:
f1 = f0 =1 ;
fn = fn-1 + fn-2 ; (n>1)
Điêù kiêṇ dừng: f(0) = f(1) = 1.
long Fibonaci (int n)
{
if(n==0 || n==1)
return 1;
return Fibonaci(n-1) + Fibonaci(n-2);
}
7
*
*Trong thân cuả ham̀ co ́lời goị ham̀ goị laị chińh no ́được đăṭ bên trong voǹg 
lăp̣.
 TenHam (́)
{
for (int i = 1; i<=n; i++)
{ //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
if (điêù kiêṇ dừng)
{ . . .
//Tra ̉vê ̀gia ́trịhay kêt́ thuć công viêc̣
}
else
{ //Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
TenHam (́); 
}
}
}
8
Vi ́du:̣ Tińh sốhaṇg thứn cuả daỹ {Xn} được điṇh nghiã
như sau:
X0 =1 ;
Xn = n2X0 + (n-1)2X1 +  + 12Xn-1 ; (n≥1)
Điêù kiêṇ dừng:X(0) = 1.
long TinhXn (int n)
{
if(n==0)
return 1;
long s = 0;
for (int i=1; i<=n; i++)
s = s + i * i * TinhXn(n-i);
return s;
}
9
*
*Trong thân cuả ham̀ naỳ co ́ lời goị ham̀ 
đêń ham̀ kia vàtrong thân cuả ham̀ kia co ́
lời goị ham̀ tới ham̀ naỳ.
10
 TenHam2 (́);
 TenHam1 (́)
{
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
TenHam2 (́); 
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
}
 TenHam2 (́)
{
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
TenHam1 (́); 
//Thực hiêṇ môṭ sốcông viêc̣ (nêú co)́
}
11
Vi ́du:̣ Tińh sốhaṇg thứn cuả hai daỹ {Xn}, {Yn} được điṇh nghiã như sau:
X0 =Y0 =1 ;
Xn = Xn-1 + Yn-1; (n>0)
Yn = n2Xn-1 + Yn-1; (n>0)
- Điêù kiêṇ dưǹg:X(0) = Y(0) = 1.
long TinhYn(int n);
long TinhXn (int n)
{
if(n==0)
return 1;
return TinhXn(n-1) + TinhYn(n-1);
}
long TinhYn (int n)
{
if(n==0)
return 1;
return n*n*TinhXn(n-1) + TinhYn(n-1);
}
12
*
*Ví dụ tính n! với n=5
13