Bài giảng "Kỹ thuật lập trình - Chương 5: Lập trình đệ quy" cung cấp cho người học các kiến thức: Giới thiệu về lập trình đệ quy, xây dựng giải thuật đệ quy, phân loại các dạng đệ quy, hoạt động của đệ quy, các giải pháp thay thế cho đệ quy. . | Lập trình C Chương 5. Lập trình đệ quy (3 tiết) Trần Minh Thái Email: minhthai@ Website: Cập nhật: 20/03/2017 Chương 0 1 Nội dung Giới thiệu về lập trình đệ quy Xây dựng giải thuật đệ quy Phân loại các dạng đệ quy Hoạt động của đệ quy Các giải pháp thay thế cho đệ quy Bài tập 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) Đị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 Giới thiệu về lập trình đệ quy Ví dụ 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)! * n 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) 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 Giới thiệu về lập trình đệ quy Để đị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 của thuật toán qua một điều kiện cụ thể (phần dừng của đệ quy) 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 !!! Phần đệ quy phải tiến về phần không đệ quy Giới thiệu về lập trình đệ quy Bước 1: Thông số hóa bài toán Bước 2: Phát hiện các trường hợp suy biến và tìm giải thuật cho bài toán này Bước 3: Phân rã bài toán theo hướng đệ quy Xây dựng giải thuật đệ quy Tổng quát hóa bài toán, tìm ra nhóm các bài toán, các thông số kích thước, thông số điều khiển. Ví dụ: thông số n trong hàm tính giai thừa, trong hàm Fibonaci, thông số a, b trong hàm tìm ước số chung lớn nhất Bước 1: Thông số hóa bài toán Là các trường hợp tương ứng với giá trị biên của biến điều khiển (trường hợp kích thước nhỏ nhất, trường hợp đặc biệt) mà không | Lập trình C Chương 5. Lập trình đệ quy (3 tiết) Trần Minh Thái Email: minhthai@ Website: Cập nhật: 20/03/2017 Chương 0 1 Nội dung Giới thiệu về lập trình đệ quy Xây dựng giải thuật đệ quy Phân loại các dạng đệ quy Hoạt động của đệ quy Các giải pháp thay thế cho đệ quy Bài tập 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) Đị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 Giới thiệu về lập trình đệ quy Ví dụ 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)! * n 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) 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 .
