Bài giảng Kỹ thuật lập trình đệ quy

Bài giảng Kỹ thuật lập trình đệ quy gồm có những nội dung chính sau: Giới thiệu về lập trình đệ quy, phân loại các dạng đệ quy, hoạt động của đệ quy, xây dựng giải thuật đệ quy, các giải thuật đệ quy tiêu biểu, các giải pháp thay thế cho đệ quy. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình đệ quy5/4/2016 1 Nội dung Giới thiệu về lập trình đệ quy Phân loại các dạng đệ quy Hoạt động của đệ quy Xây dựng giải thuật đệ quy Các giải thuật đệ quy tiêu biểu Các giải pháp thay thế cho đệ quy Tóm tắt chương5/4/2016 2 [3.1] Giới thiệu về lập trình đệ quy Khi lập trình, gặp dạng bài toán: đối tượng khó định nghĩa một cách tường minh. Kỹ thuật định nghĩa đối tượng qua chính nó: kỹ thuật đệ quy (recursion). Ví dụ: 2 chiếc gương đối diện nhau. Chiếc thứ nhất chứa hình chiếc thứ hai và ngược lại. Ta hình dung ra dãy các ảnh vô hạn của hai chiếc gương. Ví dụ: trên truyền hình, biên tập viên ngồi kế bên màn hình của chương trình đang phát, có dãy hình ảnh lập đi lập lại nhưng nhỏ dần..5/4/2016 3 [3.1] Giới thiệu về lập trình đệ quy Đệ quy được sử dụng rộng rãi trong khoa học máy tính và lý thuyết tính toán. Định nghĩa theo đệ 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ụ: về các định nghĩa đệ quy như sau: Giai thừa của n (n!):  Nếu n=0 hoặc n=1 thì n!=1.  Nếu n>1 thì n!=(n-1)! * n5/4/2016 4 [3.1] Giới thiệu về lập trình đệ quy Ký hiệu số phần tử của một hữu hạn S là |S|: Nếu S= thì |S| = 0. Nếu S≠ thì chắc chắn có một phần tử xS, khi đó |S|=|S{x}|+1. Đây là phương pháp định nghĩa tập hợp. Tập số tự nhiên: Số 1 là số tự nhiên (1N). Số tự nhiên bằng số tự nhiên cộng 1 (nN  (n+1)N).5/4/2016 5 [3.1] Giới thiệu về lập trình đệ quy Cấu trúc danh sách liên kết (linklist/xâu) kiểu T: Cấu trúc rỗng là danh sách liên kết kiểu T. Kết nối một thành phần kiểu T (nút kiểu T) vào một danh sách liên kết kiểu T, ta có một danh sách liên kết kiểu T.5/4/2016 6 [3.1] Giới thiệu về lập trình đệ quy Ví dụ trên, để định nghĩa đệ quy gồm 2 phần: Phần cố định (cơ sở - neo – anchor): các trường hợp suy biến (trường hợp đặc biệt) của thuật toán qua một điều kiện cụ thể (phần dừng của đệ quy – chương trình phải có tính dừng). Phần đệ quy (quy nạp): mô tả thuật toán trong trường hợp phổ biến qua chính đối tượng (gọi hàm đệ quy) một cách gián tiếp hay trực tiếp. Lưu ý: phần đệ quy phải tiến về phần không đệ quy.5/4/2016 7 [3.2] Phân loại đệ quy Đệ quy tuyến tính. Đệ quy nhị phân. Đệ quy phi tuyến. Đệ quy hỗ tương.5/4/2016 8 Đệ quy tuyến tính Bước 1: Nếu thỏa điều kiện dừng thì thực hiện thao tác S (trả về kết quả) Bước 2: Ngược lại: Bước 2.1 thực hiện lệnh S* Bước 2.2 Gọi hàm đệ quy (cho đối tượng thường là nhỏ hơn)S, S*: xử lý không đệ quy. Có thể gộp bước 2.1 và 2.2 lại. 5/4/2016 9 Đệ quy tuyến tính Hàm tính giai thừa (n!) Bước 1: Nếu n=0 hoặc n=1 thì trả về 1 Bước 2: Ngược lại: trả về n*Giai_thừa(n-1)5/4/2016 10 Đệ quy tuyến tính Cài đặt: int giaiThua(int n) { if (n == 1 || n == 0) return 1; return giaiThua(n - 1) * n; }5/4/2016 11 Đệ quy tuyến tính Uớc chung lớn nhất của 2 số dựa vào thuật toán Euclide:Bước 1: Nếu n=0 thì trả về mBước 2: Ngược lại: trả về USCLN(n, m mod n)5/4/2016 12 Đệ quy tuyến tính Cài đặt: int UCLN(int m, int n) { if (n == 0) return m; return uCLN(n, m% n); }5/4/2016 13 Đệ quy tuyến tính Tính tổng giá trị của dãy số nguyênBước 1: Nếu n=1 thì trả về a[n-1]Bước 2: Ngược lại: trả về a[n-1]+tongDay(a,n-1)5/4/2016 14 Đệ quy tuyến tính Cài đặt: int tongDay(int []a, int n) { if (n == 1) return a[n-1]; return a[n-1]+tongDay(a, n-1); }5/4/2016 15 Đệ quy tuyến tính Liệt kê các giá trị lẻ của dãy số nguyênBước 1: Nếu n=0 thì dừngBước 2: Ngược lại: ...