Xem mẫu
- *
Trần Minh Thái
minhthai@itc.edu.vn
1
- *
*Một hàm được gọi có tính đệ qui nếu trong
thân của hàm đó có lệnh gọi lại chính nó một
cách tường minh hay tiềm ẩn.
*Phân loại đệqui
*Đệ qui tuyến tính.
*Đệqui nhịphân.
*Đệqui phi tuyến.
*Đệqui hỗtương.
2
- *
• Trong thân hàm có duy nhất một lời gọi hàm gọi lại
chính nómột cách tường minh.
TenHam ()
{
if (điều kiện dừng)
{
...
//Trảvềgiátrịhay kết thúc công việc
}
//Thực hiện một sốcông việc (nếu có)
. . . TenHam ();
//Thực hiện một sốcông việc (nếu có)
}
3
- Vídụ: Tính S ( n ) = 1 + 2 + 3 + L + n
- Điều kiện dừng: S(0) = 0.
- Qui tắc (công thức) tính: S(n) = S(n-1) + n.
int TongS (int n)
{
if(n==0)
return 0;
return ( TongS(n-1) + n );
}
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 của hàm cóhai lời gọi hàm gọi lại chính nómột cách tường
minh.
TenHam ()
{
if (điều kiện dừng)
{
...
//Trảvềgiátrịhay kết thúc công việc
}
//Thực hiện một sốcông việc (nếu có)
. . .TenHam (); //Giải quyết vấn đềnhỏhơn
//Thực hiện một sốcông việc (nếu có)
. . . TenHam (); //Giải quyết vấn đềcòn lại
//Thực hiện một sốcông việc (nếu có)
} 6
- Vídụ: Tính sốhạng thứn của dã
y Fibonaci
được định nghĩ a như sau:
f1 = f0 =1 ;
fn = fn-1 + fn-2 ; (n>1)
Điều kiện 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 của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vòng
lặp.
TenHam ()
{
for (int i = 1; i
- Vídụ: Tính sốhạng thứn của dã
y {Xn} được định nghĩ
a
như sau:
X0 =1 ;
Xn = n2X0 + (n-1)2X1 + … + 12Xn-1 ; (n≥1)
Điều kiện dừng:X(0) = 1.
long TinhXn (int n)
{
if(n==0)
return 1;
long s = 0;
for (int i=1; i
- *
*Trong thân của hàm này có lời gọi hàm
đến hàm kia vàtrong thân của hàm kia có
lời gọi hàm tới hàm này.
10
- TenHam2 ();
TenHam1 ()
{
//Thực hiện một sốcông việc (nếu có)
…TenHam2 ();
//Thực hiện một sốcông việc (nếu có)
}
TenHam2 ()
{
//Thực hiện một sốcông việc (nếu có)
…TenHam1 ();
//Thực hiện một sốcông việc (nếu có)
}
11
- Vídụ: Tính sốhạng thứn của hai dã
y {Xn}, {Yn} được định nghĩ
a như sau:
X0 =Y0 =1 ;
Xn = Xn-1 + Yn-1; (n>0)
Yn = n2Xn-1 + Yn-1; (n>0)
- Điều kiện dừng: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
nguon tai.lieu . vn
