Bài giảng Cơ sở lập trình nâng cao - Chương 3: Lập trình Đệ quy - Tôn Quang Toại

CƠ SỞ LẬP TRÌNH NÂNG CAO 
Biên soạn: Ths.Tôn Quang Toại 
TonQuangToai@yahoo.com 
TPHCM, NĂM 2013 
TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC TP.HCM 
KHOA CÔNG NGHỆ THÔNG TIN 
LẬP TRÌNH ĐỆ QUY 
Chương 3 
Nội dung 
Định nghĩa theo cách đ ệ qu y 
Cài đặt Hàm đệ quy 
Hoạt động của Hàm đệ qu y 
Phân loại đệ quy 
Ứng dụng của đệ quy 
Ưu điểm và khuyết điểm của đệ quy 
Một số phương pháp khử đệ quy 
Bài tập áp dụng 
Định nghĩa theo c á ch đ ệ qu y 
Định nghĩa theo c á ch đệ quy: Định nghĩa theo cách đệ quy của một khái niệm là định nghĩa khái niệm mới đó thông qua chính khái niệm đang muốn định nghĩa. 
Ví dụ: Định nghĩa tập số tự nhiên N 
0 N 
Nếu n N thì n+1 N 
Định nghĩa theo c á ch đ ệ qu y 
Mục đích của đệ quy: 
Tạo ra các phần tử mới 
Kiểm tra một phần tử có thuộc tập đã cho hay không 
Dùng định nghĩa theo cách đệ quy để định nghĩa các hàm hay chuỗi số (Hàm đệ quy, công thức đệ quy) 
Ví dụ 1: 
Nếu n=0 
Nếu n>0 
Định nghĩa theo c á ch đ ệ qu y 
Ví dụ 2: 
Nếu n=0 
Nếu n>0 
Ví dụ 3 : Công thức tính số Fibonacci 
Nếu n>2 
Nếu n=1 hay n=2 
Định nghĩa theo c á ch đ ệ qu y 
Các thành phần của 1 định nghĩa theo cách đệ quy 
Thành phần 1: Thành phần không đệ qu y (trường hợp cơ bản, trường hợp cơ sở, tr ườ ng h ợ p suy bi ế n, điều kiện dừng ) 
Chứa những trường hợp đơn giản nhất để xây dựng nên tập hợp 
Thành phần 2: Thành phần đệ qu y (trường hợp đệ quy) 
Chứa những quy tắc, công thức để tạo đối tượng mới từ những đối tượng trước đó 
Nhận xét: Thành phần đệ qu y phải tiến về thành phần không đệ qu y 
Định nghĩa theo c á ch đ ệ qu y 
Làm thế nào để tìm công thức đệ quy? 
Chia bài toán f(n) thành các bài toán con f(1), f(2), , f(n-1) có dạng giống bài toán f(n) 
Tìm mối quan hệ giữa bài toán lớn với bài toán con 
Vấn đề khó khăn 
Bao nhiêu bài toán con? 
Chọn bài toán con nào? 
Định nghĩa theo c á ch đ ệ qu y 
Các bước gợi ý tìm công thức đệ quy f(n) 
B1: Chọn một bài toán con f(k) 	(thường là f(n-1), f(n-2)) 
B2: Tìm mối quan hệ giữa f(n) với f(k) 
B3: Nếu tìm được mối quan hệ thì 	Tìm trường hợp cơ sở	Nhảy đến B5 
B4: Ngược lại quay về B1 chọn bài toán con khác, nếu thấy không khả quan thì chọn một số bài toán con 
B5: Kết thúc 
Định nghĩa theo c á ch đ ệ qu y 
Tìm định nghĩa đệ quy để tính tổng/tích của mảng số nguyên a có n phần tử (n ≤ 100) 
Định nghĩa theo c á ch đ ệ qu y 
Tìm định nghĩa đệ quy để kiểm tra số nguyên n là số chẵn hay số lẻ (không dùng phép toán % và &) 
Định nghĩa theo c á ch đ ệ qu y 
Tìm định nghĩa đệ quy để tính độ dài của chuỗi s 
Định nghĩa theo c á ch đ ệ qu y 
Tìm định nghĩa đệ quy để kiểm tra chuỗi s có chứa ký tự ch không 
Định nghĩa theo c á ch đ ệ qu y 
Tìm định nghĩa đệ quy để đảo mảng số nguyên a có n phần tử (n ≤ 100) 
Định nghĩa theo c á ch đ ệ qu y 
Hạn chế của định nghĩa Đệ quy 
Để tính f(n), chúng ta phải tính một vài hay tất cả các phần tử trước đó f(1), f(2),  
Để kiểm tra x có thuộc tập hợp đang định nghĩa hay không chúng ta cũng phải tính f(1), f(2),  
Tìm định nghĩa không đệ quy tương đương 
Định nghĩa theo c á ch đ ệ qu y 
Tìm định nghĩa không đệ quy của công thức đệ quy sau: 
Nếu n=0 
Nếu n>0 
Nếu n=0 
Nếu n>0 
Cài đặt Hàm đệ quy 
Hàm /th ủ t ụ c Đệ qu y : Một hàm A được gọi là Hàm Đệ qu y nếu trong định nghĩa hàm A có lời gọi đến chính hàm A 
KieuTraVe TenHam(Danh Sach Tham So){		 TenHam() ;	} 
Cài đặt Hàm đệ quy 
Sơ đồ cài đặt 
Sơ đồ 1: 
KieuTraVe TenHam(Kieu n){	 if ( dieukien dung )	[ return ] kq;	 else 	[ return ] TenHam(n-1) } 
Cài đặt Hàm đệ quy 
Sơ đồ cài đặt 
Sơ đồ 2: 
KieuTraVe TenHam(Kieu n){	 if ( dieukien dequy )	[ return ] TenHam(n-1);	 else 	[ return ] kq;} 
Cài đặt Hàm đệ quy 
Ví dụ: Cài đặt hàm đệ quy tính n! 
int Factorial( int n){} 
Hoạt động của Hàm đệ qu y 
Tìm hiểu hoạt động của hàm đệ quy tính a n 
Nếu n=0 
Nếu n>0 
double Power( double a, int n){} 
Hoạt động của Hàm đệ qu y 
Phân tích hoạt động của hàm Power(a, n) một cách hình thức: 
Gồm 2 pha: 
Pha tiến (forward): Tiến đến lời giải nhỏ nhất 
Pha lùi (backward): Kết hợp các kết quả lại với nhau 
Ví dụ: Cho a= 5, n=3, hãy theo vết chạy của hàm Power(5, 3) 
Hoạt động của Hàm đệ qu y 
Power(5, 3) 
return 5 * Power(5, 2) 
return 5 * Power(5, 1) 
return 5 * Power(5, 0) 
return 1 
Hoạt động của Hàm đệ qu y 
Hoạt động của hệ thống: 
Hệ thống lưu giữ trạng thái của tất cả các lời gọi hàm trong ngăn xếp 
Mỗi khi có một lời gọi hàm, hệ thống tạo ra 1 vùng lưu trữ trong ngăn xếp gọi là bản ghi kích hoạt (activation record) để lưu thông tin 
Giá trị trả về 
Địa chỉ trả về 
Địa chỉ các liên kết động 
Tham số truyền vào 
Các biến cục bộ 
Hoạt động của Hàm đệ qu y 
Phân loại đệ quy 
Đệ quy có thể được phân thành một số trường hợp sau: 
Đệ quy trực tiếp 
Đệ quy gián tiếp 
Đệ quy tuyến tính 
Đệ quy nhánh (đệ quy không tuyến tính, đệ quy cây) 
Đệ quy đuôi 
Đệ quy lồng nhau 
Phân loại đệ quy Đệ quy trực tiếp 
Định nghĩa [Đệ quy trực tiếp – Direct Recursion]: Một hàm được gọi là Hàm Đệ quy trực tiếp nếu hàm đó có lời gọi đến chính nó một cách rõ ràng 
Ví dụ: 
int Foo (int x){ if (x <= 0) return x; return Foo(x – 1); 
} 
Phân loại đệ quy Đệ quy gián tiếp 
Định nghĩa [Đệ quy gián tiếp – Indirect Recursion]: Một hàm được gọi là Hàm Đệ quy gián tiếp nếu hàm đó gọi đến nó thông qua những lời gọi hàm khác 
Sơ đồ	f() g 1 () g 2 ()  g n () f() 
Phân loại đệ quy Đệ quy gián tiếp 
Ví dụ: 
int Foo( int x){ if (x <= 0) 	 return x; return Bar(x);} 
int Bar( int y){ return Foo (y – 1);} 
Phân loại đệ quy Đệ quy tuyến tính 
Định nghĩa [Đệ quy tuyến tính – Linear Recursion]: Một hàm đệ quy được gọi là đệ quy tuyến tính nếu hàm đó không có toán tử phụ thuộc vào 2 lời gọi đệ quy trở lên 
int Factorial (int n){ if (n == 0) 	 return 1; return n * Factorial(n – 1);} 
Phân loại đệ quy Đệ quy nhánh 
Định nghĩa [Đệ quy nhánh – Tree Recursion]: Một hàm đệ quy được gọi là đệ quy nhánh nếu hàm đó có toán tử phụ thuộc vào 2 lời gọi đệ quy trở lên 
int Fibonacci ( int n){ if (n==1 || n==2) 	 return 1; 
 return Fibonacci(n – 1) + Fibonacci(n-2);} 
Phân loại đệ quy Đệ quy đuôi 
Định nghĩa [Đệ quy đuôi – Tail Recursion]: Hàm Đệ quy đuôi là một hàm đệ quy thỏa: 
Chứa duy nhất 1 lời gọi đệ quy 
Lời gọi đệ quy nằm ở cuối hàm 
Lời gọi đệ quy trước không phụ thuộc lời gọi đệ quy sau 
Ví dụ: 
void InSo(int n){	 if (n>0)	{	cout << n; 	InSo(n-1);	}} 
Phân loại đệ quy Đệ quy lồng nhau 
Định nghĩa [Đệ quy lồng nhau]: Hàm Đệ quy lồng nhau là hàm gọi đến chính nó và sử dụng chính hàm đó như là tham số đầu vào của hàm 
Ví dụ: 
Nếu n=0 
Nếu n>0 , m=0 
Nếu n , m >0 
Ứng dụng của đệ quy 
Lập trình đệ quy được dùng trong một số trường hợp sau 
Dùng trong phương pháp chia để trị 
Dùng trong phương pháp quy hoạch động 
Dùng trong phương pháp quay lui vét cạn 
Ưu điểm và khuyết điểm của đệ quy 
Ưu điểm 
Trong sáng 
Dễ đọc 
Cài đặt đơn giản, ngắn gọn 
Khuyết điểm 
Phải lưu nhiều trạng thái trong stack: Có thể tràn ngăn xếp 
Làm chậm thời gian thực thi chương trình 
Một số phương pháp khử đệ quy 
Một số gợi ý: 
Tìm công thức không đệ quy 
Dùng mảng lưu trữ dữ liệu trung gian 
Dùng stack để mô phỏng đệ quy 
Bài tập áp dụng 
Viết hàm đệ quy Tính Ước số chung lớn nhất của a và b (USCLN(a, b)) 
Nếu b=0 
Nếu b≠0 
Nếu k=0 hay n=k 
Nếu 0<k<n 
Viết hàm đệ quy tính 
Bài tập áp dụng 
Viết hàm đệ quy In mảng a gồm n phần tử (n ≤ 100) lên màn hình 
Viết hàm đệ quy In ra các chữ số của số nguyên n theo thứ tự đảo ngược 
Viết hàm đệ quy Tìm số lớn nhất /nhỏ nhất của mảng số nguyên a có n phần tử (n ≤ 100) 
Viết hàm đệ quy Đếm số lần xuất hiện của ký tự ch trong chuỗi s 
Bài tập áp dụng 
Viết hàm đệ quy Kiểm tra n có phải là số nguyên tố không 
Viết hàm đệ quy Giải bài toán tháp Hanoi 
Viết hàm đệ quy liệt kê các phân số tối giản không giảm nằm trong [0, 1] và có mẫu số nhỏ hơn hay bằng n 
Viết hàm đệ quy Tính giá trị của một số viết dưới dạng chữ LA MÃ 
HẾT CHƯƠNG 3