Bài giảng C căn bản - Chương 3: Kỹ thuật đệ qui

Ch ương 3  Kỹ thuật đệ qui 
3.1. Khái niệm đệ quy 
Một hàm gọi đến chính hàm đó thì được gọi là đệ qui 
Định nghĩa số tự nhiên 
	0 là số tự nhiên bé nhất . 
	 Nếu k là số tự nhiên thì k + 1 cũng là số tự nhiên 
	 Như vậy , số tự nhiên bắt đầu từ 0, ta có các số tự nhiên là : 0 + 1 = 1, 1 + 1 = 2, 
Chuỗi ký tự 
	 Chuỗi rỗng là một chuỗi ký tự . 
	 Một chuỗi ký tự ghép với một ký tự bất kỳ là một chuỗi ký tự . 
2 
3.1. Khái niệm đệ quy 
Tính giai thừa, n! 
	Khi n = 0 thì n! = 1 
	Khi n > 0 thì n! = (n - 1)! * n 
Ước chung lớn nhất của hai số nguyên không âm m, n (với m >n) như sau: 
	Nếu n = 0 thì UCLN(m, n) = m 
	Nếu n ≠ 0 thì UCLN(m, n) = UCLN(n, m mod n) 
3 
3.2. Hàm đệ quy 
Hai bước giải bài toán đệ quy 
	Bước 1 : Phân tích bài toán thành bài toán đồng dạng nhưng đơn giản hơn và dừng lại ở bài toán đồng dạng đơn giản nhất có thể xác định ngay kết quả. 
	Bước 2 : Xác định kết quả bài toán đồng dạng từ đơn giản đến phức tạp để có kết quả cuối cùng. 
4 
3.2. Hàm đệ quy 
Cấu trúc hàm đệ quy 
 () 
{	 
	if () 
	{ 
	 return ; 
	} 
	... Gọi lại hàm với tham số bé hơn 
	... 
} 
5 
3.2. Hàm đệ quy 
Viết hàm tính n!, với n  0 
	long	Fac(int n) 
	{	if(n == 0) 
	return 1; 
	return n*Fac(n – 1); 
	} 
6 
3.2. Hàm đệ quy 
Đệ quy 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 . 
	 () 
	{ 
	 	if () 
	{ 
	 return ; 
	} 
	 ();  
	} 
7 
3.3. Phân loại đệ qui 
Đệ quy tuyến tính 
Tính S(n) = 1 + 2 +  + n 
	S(n) = S(n – 1) + n 
	Điều kiện dừng: S(0) = 0 
	long Tong(int n) 
	{ 	 
	if (n == 0) 
	return 0; 
	return Tong(n –1) + n; 
	} 
8 
3.3. Phân loại đệ qui 
Đệ quy nhị phân 
	 Trong thân hàm có hai lời gọi hàm gọi lại chính nó một cách tường minh . 
	 () 
	{ 
	if () 
	{ 
	 	 return ; 
	} 
	 ();  
	 ();  
	} 
9 
3.3. Phân loại đệ qui 
Đệ quy nhị phân 
	 Tính số hạng thứ n của dãy Fibonacy 
	f(0) = f(1) = 1 và f(n) = f(n – 1) + f(n – 2) n > 1 
	Điều kiện dừng: f(0) = 1 và f(1) = 1 
	long Fibo(int n) 
	{ 
	if (n == 0 || n == 1) 
	return 1; 
	return Fibo(n –1) + Fibo(n –2); 
	} 
10 
3.3. Phân loại đệ qui 
Đệ quy hỗ tương 
	 Trong thân hàm này có lời gọi hàm tới hàm kia và ngược lại 
	 () 
	{ 	if () 
	{ 
	 return ; 
	} 
	 ();  
	} 
	} 
	 () 
	{ 	if () 
	{ 
	 return ; 
	} 
	 ();  
	} 
11 
3.3. Phân loại đệ qui 
Đệ quy hỗ tương 
	 Tính số hạng thứ n của dãy sau : 
	 	 x(0) = 1, y(0) = 0 
	x(n) = x(n – 1) + y(n – 1) 
	y(n) = 3*x(n – 1) + 2*y(n – 1) 
	 Điều kiện dừng: x(0) = 1, y(0) = 0 
long xn(int n) 
	{ 	if (n == 0) return 1; 
	return xn(n-1) + yn(n-1); 
	} 
long yn(int n) 
	{ 
	if (n == 0) return 0; 
	return 3*xn(n-1) + 2*yn(n-1); 
	} 
12 
3.3. Phân loại đệ qui 
Đệ quy phi tuyến 
	 Trong thân hàm có lời gọi hàm lại chính nó được đặt bên trong thân vòng lặp . 
	 () 
	{ 
	if () 
	{ 
	 return ; 
	} 
	 Vòng lặp 
	{ 
	 (); 
	} 
	} 
13 
3.3. Phân loại đệ qui 
Đệ quy phi tuyến 
	Tính số hạng thứ n của dãy: 
	x(0) = 1 
	x(n) = n 2 x(0) + (n-1) 2 x(1) +  + 2 2 x(n – 2) + 1 2 x(n – 1) 
	Điều kiện dừng: x(0) = 1 
long xn(int n) 
{ 
 	if (n == 0) 
	return 1; 
	long s = 0; 
	for (int i=1; i<=n; i++) 
	s = s + i*i* xn(n –i); 
	return s; 
} 
14 
3.4. Các bước xây dựng hàm đệ quy 
Bước 1: Thông số hóa bài toán . 
	 Tổng quát hóa bài toán cụ thể thành bài toán tổng quát . 
	 Thông số hóa bài toán tổng quát . 
	Ví dụ: n trong hàm tính tổng S(n) = 1 + 2 + 3 +  + n 
Bước 2: Tìm thuật giải tổng quát. 
	Phần không đệ quy. 
	Phần như bài toán trên nhưng kích thước nhỏ hơn. 
	Ví dụ: S(n) = S(n – 1) + n 
Bước 3: Tìm các trường hợp suy biến. 
	Các trường hợp suy biến của bài toán. 
	Kích thước bài toán trong trường hợp này là nhỏ nhất. 
	Ví dụ: S(0) = 0 
15 
3.5. Một số lỗi thường gặp 
Công thức đệ quy chưa đúng, không tìm được bài toán đồng dạng đơn giản hơn 
Không xác định các trường hợp suy biến – neo ( điều kiện dừng ). 
Thông điệp thường gặp là StackOverflow do: 
Thuật giải đệ quy đúng nhưng số lần gọi đệ quy quá lớn làm tràn STACK. 
Thuật giải đệ quy sai do không hội tụ hoặc không có điều kiện dừng. 
16 
3.6. Các vấn đề đệ quy thường gặp 
Truy hồi 
	Hệ thức truy hồi của 1 dãy An là công thức biểu diễn phần tử An thông qua 1 hoặc nhiều số hạng trước của dãy. 
	Gửi ngân hàng 1000 USD, lãi suất 12%/năm. Tính số tiền có được sau 30 năm. Gọi An là số tiền có được sau n năm. Ta có : 
	An = An – 1 + 0.12*An – 1 = 1.12*An – 1 
	A(0) = 1000 
	Đệ quy tuyến tính với A(n)=1.12*A(n – 1) và điều kiện dừng A(0) = 1000 
17 
3.6. Các vấn đề đệ quy thường gặp 
Chia để trị 
// Tìm nghiệm x của bài toán A. 
void	 DivideConquer(A , x) 
{ 
	if (A đủ nhỏ ) Solve(A ); 
	else 
	{	 Phân A thành các bài toán con A1, A2, , Am 
	 for ( i = 1; i <= n; i++)	DivideConquer(Ai, xi); 
	Kết hợp các nghiệm xi của Ai để nhận được x của A. 
	} 
} 
18 
3.6. Các vấn đề đệ quy thường gặp 
Phương pháp quay lui 
Tại bước có nhiều lựa chọn , ta chọn thử 1 bước để đi tiếp . 
Nếu không thành công thì “ lần ngược ” chọn bước khác . 
Nếu đã thành công thì ghi nhận lời giải này đồng thời “ lần ngược ” để truy tìm lời giải mới . 
Thích hợp giải các bài toán kinh điển như bài toán 8 hậu và bài toán mã đi tuần . 
19 
Tổng kết 
Chỉ nên dùng phương pháp đệ quy để giải các bài toán kinh điển như giải các vấn đề “ chia để trị ”, “ lần ngược ”. 
Vấn đề đệ quy không nhất thiết phải giải bằng phương pháp đệ quy , có thể sử dụng phương pháp khác thay thế ( khử đệ quy ) 
Phương pháp đệ qui tiện cho người lập trình nhưng không tối ưu khi chạy trên máy . 
Bước đầu nên giải bằng đệ quy nhưng từng bước khử đệ quy để nâng cao hiệu quả . 
20 
Q&A 
21