tailieunhanh - Bài giảng Kỹ thuật lập trình: Kỹ thuật đệ qui - ThS. Đặng Bình Phương (ĐH Khoa học Tự nhiên)

Bài giảng Kỹ thuật lập trình - Kỹ thuật đệ qui cung cấp cho người học các kiến thức: Giới thiệu về lập trình đệ qui, phân loại các dạng đệ qui, một số ứng dụng của giải pháp đệ qui, những ví dụ về giải pháp thay thế cho đệ qui, đồ án lập trình,. nội dung chi tiết. | Bài giảng Kỹ thuật lập trình: Kỹ thuật đệ qui - ThS. Đặng Bình Phương (ĐH Khoa học Tự nhiên) Kỹ thuật lập trình ThS. Đặng Bình Phương (dbphuong@) Giới thiệu về lập trình đệ qui Phân loại các dạng đệ qui Một số ứng dụng của giải pháp đệ qui Những ví dụ về giải pháp thay thế cho đệ qui Đồ án lập trình Các vấn đề tìm hiểu mở rộng kiến thức nghề nghiệp Thuật ngữ và bài đọc thêm tiếng Anh 2/27/2014 Khoa CNTT - ĐH Khoa học tự nhiên 2 • Cho S(n) = 1 + 2 + 3 + + n • Tính S(10) và S(11) S(10) = 1 + 2 + + 10 = 55 S(11) = 1 + 2 + + 10 + 11 = 66 = S(10) + 11 = 55 + 11 = 66 2/27/2014 Khoa CNTT - ĐH Khoa học tự nhiên 4 • Khái niệm – Vấn đề đệ quy là vấn đề được định nghĩa bằng chính nó. • 2 điều kiện quan trọng – Tồn tại bước đệ qui – Điều kiện dừng • Ví dụ trong bài toán trước thì: – Bước đệ qui: S(n) = S(n – 1) + n – Điều kiện dừng: S(1) = 1 2/27/2014 Khoa CNTT - ĐH Khoa học tự nhiên 5 • Đệ qui tuyến tính (đệ qui thông thường và đệ qui đuôi): Trong thân hàm có duy nhất một lời gọi hàm gọi lại chính nó một cách tường minh. • Đệ qui nhị phân: Trong thân hàm có hai lời gọi hàm gọi lại chính nó một cách tường minh. • Đệ qui hỗ tương: Trong thân hàm này có lời gọi hàm tới hàm kia và bên trong thân hàm kia có lời gọi hàm tới hàm này. • Đệ qui phi tuyến: Trong thân hàm có lời gọi hàm lại chính nó nằm bên trong thân vòng lặp. 2/27/2014 Khoa CNTT - ĐH Khoa học tự nhiên 7 • Tính S(n) = 1 + 2 + + n – S(n) = S(n – 1) + n – S(0) = 0 long Tong(int n) { if (n == 0) return 0; return Tong(n – 1) + .