Bài giảng "Kỹ thuật lập trình: Đệ quy" cung cấp cho người học các kiến thức: Các vấn đề đệ quy thông dụng, khái niệm, phân loại, đệ quy và chia để trị, bài toán tháp Hà Nội, bài toán Edit distance,. . | Bài giảng Kỹ thuật lập trình: Đệ quy - Trịnh Tấn Đạt Đệ Quy (Recursion) Trịnh Tấn Đạt Khoa CNTT - Đại Học Sài Gòn Email: trinhtandat@ Website: Nội dung ▪ Khái niệm ▪ Phân loại ▪ Các vấn đề đệ quy thông dụng ▪ Đệ quy và chia để trị ▪ Bài toán tháp hà nội ▪ Đệ quy và quy lui (option) ▪ Bài toán Edit distance (option) ▪ Bài toán Closet pairs of points (option) ▪ Bài Tập Đệ Quy ▪ Đệ quy là kỹ thuật đưa bài toán hiện tại về một bài toán cùng loại, cùng tính chất (đồng dạng) nhưng ở cấp độ thấp hơn. Quá trình này tiếp tục cho đến khi bài toán được đưa về một cấp độ mà tại đó có thể giải được. Từ cấp độ này ta lần ngược lại để giải các bài toán ở cấp độ cao hơn cho đến khi giải xong bài toán ban đầu. ▪ Ví dụ: Định nghĩa n giai thừa: n! = 1*2*3*4*5* *n → định nghĩa tự nhiên n*(n-1)! với 0!=1 → định nghĩa bằng đệ quy Đệ Quy Các ứng dụng ▪ Hình học fractal ▪ Game candy crush ▪ Structure “Tree” ▪ Koch snowflake Candy Crush Đệ Quy - Khái niệm ▪ Kỹ thuật đệ quy: là kỹ thuật định nghĩa một khái niệm có sử dụng chính khái niệm đang cần định nghĩa. ▪ Hàm đệ quy: là hàm mà trong thân của nó có lệnh gọi lại chính nó dành cho đối tượng ở cấp thấp hơn. ▪ Ví dụ: Hàm tính n! Đệ quy S = 1+2+3+ +n ▪ Hai yếu tố cần để tiến hành một phương thức đệ quy là: o Có điều kiện dừng (phần cơ sở, phần neo): Xác định quy luật của phương thức và tìm giá trị cụ thể khi thỏa mãn một điều kiện nhất định. Nếu hàm đệ quy không có phần này thì hàm sẽ bị lặp vô hạn và sinh lỗi khi thực hiện. o Phương thức đệ quy: Phương thức đệ quy sẽ gọi lại chính nó nhưng dành cho cấp độ thấp hơn. cho đến khi nó trả về điều kiện dừng ở bước 1. Ví dụ Tính giai thừa n! #include using namespace std; int factorial(int n) { if (n == 1) //phần neo Vòng lặp vô tận return 1; else #include return (n * factorial(n - 1)); // phần đệ quy using namespace std; } int main() { void p() { cout
