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

Nội dung text: 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

1. 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
2. Chương 3 LẬP TRÌNH ĐỆ QUY
3. Nội dung • Định nghĩa theo cách đệ quy • Cài đặt Hàm đệ quy • Hoạt động của Hàm đệ quy • 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
4. Định nghĩa theo cách đệ quy • Đị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
5. Định nghĩa theo cách đệ quy • 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: 1 Nếu n=0 n!= n . (n −1)! Nếu n>0
6. Định nghĩa theo cách đệ quy – Ví dụ 2: 1 Nếu n=0 f (n) = 1 f (n −1) + Nếu n>0 f (n −1) • Ví dụ 3: Công thức tính số Fibonacci 1 Nếu n=1 hay n=2 f (n) = f (n −1) + f (n − 2) Nếu n>2
7. Định nghĩa theo cách đệ quy • 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 đệ quy (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 đệ quy (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 đệ quy phải tiến về thành phần không đệ quy
8. Định nghĩa theo cách đệ quy • 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?
9. Định nghĩa theo cách đệ quy • 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
10. Định nghĩa theo cách đệ quy • 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)
11. Định nghĩa theo cách đệ quy • 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à &)
12. Định nghĩa theo cách đệ quy • Tìm định nghĩa đệ quy để tính độ dài của chuỗi s
13. Định nghĩa theo cách đệ quy • Tìm định nghĩa đệ quy để kiểm tra chuỗi s có chứa ký tự ch không
14. Định nghĩa theo cách đệ quy • Tìm định nghĩa đệ quy để đảo mảng số nguyên a có n phần tử (n≤100)
15. Định nghĩa theo cách đệ quy • 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
16. Định nghĩa theo cách đệ quy • Tìm định nghĩa không đệ quy của công thức đệ quy sau: 1 Nếu n=0 n!= n . (n −1)! Nếu n>0 1 Nếu n=0 f (n) = 2 . f (n −1) Nếu n>0
17. Cài đặt Hàm đệ quy • Hàm/thủ tục Đệ quy: Một hàm A được gọi là Hàm Đệ quy 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(); }
18. 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) }
19. 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; }
20. Cài đặt Hàm đệ quy • Ví dụ: Cài đặt hàm đệ quy tính n! int Factorial(int n) { }
21. Hoạt động của Hàm đệ quy • Tìm hiểu hoạt động của hàm đệ quy tính an Nếu n=0 n 1 a = n−1 a . a Nếu n>0 double Power(double a, int n) { }
22. Hoạt động của Hàm đệ quy • 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)
23. Hoạt động của Hàm đệ quy Power(5, 3) return 5 * Power(5, 2) return 5 * Power(5, 1) return 5 * Power(5, 0) return 1
24. Hoạt động của Hàm đệ quy • 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ộ
25. Hoạt động của Hàm đệ quy
26. 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
27. 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); }
28. 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() → g1() → g2() → → gn() → f()
29. 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); }
30. 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); }
31. 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); }
32. 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 void InSo(int n) { if (n>0) { • Ví dụ: cout << n; InSo(n-1); } }
33. 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ụ: m +1 Nếu n=0 A(n,m) = A(n −1,1) Nếu n>0, m=0 A(n −1, A(n,m −1)) Nếu n, m>0
34. Ứ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 –
35. Ư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
36. 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 –
37. 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)) a Nếu b=0 USCLN(a,b) = USCLN(b,a mod b) Nếu b≠0 k ▪ Viết hàm đệ quy tính Cn Nếu k=0 hay n=k k 1 Cn = k k−1 Nếu 0<k<n Cn−1 +C n−1
38. 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
39. 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Ã