Bài giảng Kỹ thuật lập trình nâng cao - Chương 3: Lập trình đệ qui - Dương Thành Phết

Chƣơng 3 
LẬP TRÌNH ĐỆ QUI 
KỸ THUẬT LẬP TRÌNH NÂNG CAO 
TRƢỜNG CAO ĐẲNG CNTT TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
Giảng Viên: ThS. Dƣơng Thành Phết 
Email: phetcm@gmail.com 
Website:  
Tel: 0918158670 – facebook.com/DuongThanhPhet 
1. KHÁI NIỆM 
 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 
2. ĐỆ QUI TUYẾN TÍNH 
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. 
3 
 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ó) 
} 
long TongS (int n) 
{ 
 if(n==0) 
 return 0; 
 return ( TongS(n-1) + n ); 
} 
nnS 321)(
4 
Ví dụ: Tính 
- Điều kiện dừng: S(0) = 0. 
- Qui tắc (công thức) tính: S(n) = S(n-1) + n. 
2. ĐỆ QUI TUYẾN TÍNH 
3. ĐỆ QUI NHỊ PHÂN 
 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ó) 
 . . . 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ó) 
} 
 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. 
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. 
6 
long Fibonaci (int n) 
{ 
 if(n==0 || n==1) 
 return 1; 
 return Fibonaci(n-1) + 
Fibonaci(n-2); 
} 
3. ĐỆ QUI NHỊ PHÂN 
4. ĐỆ QUI PHI TUYẾN 
 TenHam () 
{ 
 for (int i = 1; i<=n; i++) 
 { 
 //Thực hiện một số công việc (nếu có) 
 if (điều kiện dừng) 
 //Trả về giá trị hay kết thúc công việc 
 else 
 { 
 //Thực hiện một số công việc (nếu có) 
 TenHam (); 
 } 
 } 
} 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. 
Ví dụ: Tính số hạng thứ n của dãy {Xn} được định nghĩa 
như sau: 
 X0 =1 ; 
 Xn = n
2X0 + (n-1)
2X1 +  + 1
2Xn-1 ; (n≥1) 
Điều kiện dừng:X(0) = 1. 
8 
4. ĐỆ QUI PHI TUYẾN 
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; 
} 
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. 
g()
f()
h()
f()
f() g()
9 
5. ĐỆ QUI TƢƠNG HỖ 
 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ó) 
} 
10 
5. ĐỆ QUI TƢƠNG HỖ 
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 = n
2Xn-1 + Yn-1; (n>0) 
Điều kiện dừng:X(0) = Y(0) = 1. 
5. ĐỆ QUI TƢƠNG HỖ 
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 
5. ĐỆ QUI TƢƠNG HỖ 
6. CÁCH HOẠT ĐỘNG HÀM ĐỆ QUI 
Ví dụ: tính n! với n=5 
5n 5n 4n 3n 2n
GiaiThua(5)main()
5 4 23 1
12624120
GiaiThua(2)GiaiThua(4) GiaiThua(3)
1n
GiaiThua(1)
13 
14 
 The End.