Tài liệu Kỹ thuật lập trình đệ quy

Tài liệu giảng dạy về lập trình đã được giảng dạy với mục đích cung cấp cho sinh viên những kiến thức cơ bản nhất, có tính hệ thống liên quan tới lập trình. Thông qua cuốn tài liệu này, chúng tôi muốn giới thiệu với các bạn đọc về kỹ năng lập trình cơ bản.Mời các bạn cùng tham khảo
Nội dung trích xuất từ tài liệu:
Tài liệu Kỹ thuật lập trình đệ quyTrường Đại học Khoa học Tự nhiênKhoa Công nghệ thông tinBộ môn Tin học cơ sở TIN HỌC CƠ SỞ 2 Đặng Bình Phương dbphuong@fit.hcmuns.edu.vn KỸ THUẬT LẬP TRÌNH ĐỆ QUY 1 & & Nội dungVCVC BB BB 1 Tổng quan về đệ quy 2 Các vấn đề đệ quy thông dụng 3 Phân tích giải thuật & khử đệ quy 4 Các bài toán kinh điển 2 Tin học cơ sở 2 - Đặng Bình Phương & & Bài toánVCVC BB BB  Cho S(n) = 1 + 2 + 3 + … + n =>S(10)? S(11)? S(10) = 1 + 2 + … + 10 = 55 S(11) = 1 + 2 + … + 10 + 11 = 66 S(10) + 11 = = 55 + 11 = 66 3 Tin học cơ sở 2 - Đặng Bình Phương & & 2 bước giải bài toánVCVC BB BB Bước 2. Thế ngược  Xác định kết quả bài toán đồng dạng từ đơn giản đến phức tạp = S(n-1) + n S(n)  Kết quả cuối cùng. = S(n-2) + n-1 S(n-1) = +… … … Bước 1. Phân tích = S(0) + 1 S(1)  Phân tích thành bài toán đồng dạng nhưng đơn giản hơn. =0 S(0)  Dừng lại ở bài toán đồng dạng đơn giản nhất có thể xác định ngay kết quả. 4 Tin học cơ sở 2 - Đặng Bình Phương & & Khái niệm đệ quyVCVC BB BB Khái niệm Một khái niệm X gọi là được định nghĩa theo đệ quy nếu trong định nghĩa X có sử dụng ngay chính khái niệm X . Ví dụ Tổng S(n) được tính thông qua tổng S(n-1). 2 điều kiện quan trọng Tồn tại bước đệ quy. Điều kiện dừng. 5 Tin học cơ sở 2 - Đặng Bình Phương & & Hàm đệ quy trong NNLT CVCVC BB BB  Khái niệm  Một hàm được gọi là đệ quy nếu bên trong thân của hàm đó có lời gọi hàm lại chính nó một cách trực tiếp hay gián tiếp. … Hàm(…) … Hàm1(…) … Hàm2(…) { { { … … … … … … Lời gọi Hàm Lời gọi Hàm2 Lời gọi Hàmx … … … … … … … … … } } } ĐQ trực tiếp ĐQ gián tiếp 6 Tin học cơ sở 2 - Đặng Bình Phương & & Cấu trúc hàm đệ quyVCVC BB BB (TS) { Phần dừng if () step) (Base • Phần khởi tính toán hoặc { điểm kết thúc của thuật toán … • Không chứa hàm đang được return ; } Phần đệ quy … (Recursion step) … Lời gọi Hàm• Có sử dụng hàm đang được định nghĩa. … } 7 ...