Bài giảng Phương pháp lập trình: Bài 8 - TS. Ngô Hữu Dũng

Bài giảng Phương pháp lập trình: Bài 8 do TS. Ngô Hữu Dũng biên soạn trình bày các nội dung sau: Khái niệm đệ quy, hàm đệ quy trong NNLT C, cấu trúc hàm đệ quy, đệ quy tuyến tính, đệ quy nhị phân, đệ quy hỗ tương,...
Nội dung trích xuất từ tài liệu:
Bài giảng Phương pháp lập trình: Bài 8 - TS. Ngô Hữu DũngTRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINHPhương pháp lập trìnhĐệ quyTS. Ngô Hữu DũngBài toánCho S(n) = 1 + 2 + 3 + … + n=>S(10)? S(11)?S(10)= 1 + 2 + … + 10 = 55S(11)= 1 + 2 + … + 10 + 11 = 66=S(10)=55+ 11+ 11 = 66Phương pháp lập trình - Đệ quy2 bước giải bài toánBước 2. Thế ngượcS(n)= S(n-1) +S(n-1) Xác định kết quả bài toánđồng dạng từ đơn giản đếnphức tạp  Kết quả cuối cùng.n= S(n-2) + n-1…Bước 1. Phân tích=…S(1) Phân tích thành bài toán đồngdạng nhưng đơn giản hơn. Dừng lại ở bài toán đồngdạng đơn giản nhất có thể xácđịnh ngay kết quả.+ …=Phương pháp lập trình - Đệ quyS(0)+1S(0)=0Khái niệm đệ quyKhái niệmVấn đề đệ quy là vấn đề đượcđịnh nghĩa bằng chính nó.Ví dụTổng S(n) được tính thông quatổ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.Phương pháp lập trình - Đệ quyHàm đệ quy trong NNLT C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(…){……Lời gọi Hàm………}ĐQ trực tiếp… Hàm1(…){……Lời gọi Hàm2………}… Hàm2(…){……Lời gọi Hàmx………}ĐQ gián tiếpPhương pháp lập trình - Đệ quy