tailieunhanh - 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,. | TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Phương pháp lập trình Đệ quy TS. Ngô Hữu Dũng Bài toán 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) = 55 + 11 + 11 = 66 Phương pháp lập trình - Đệ quy 2 bước giải bài toán Bước 2. Thế ngược S(n) = S(n-1) + S(n-1) Xác định kết quả bài toán đồng dạng từ đơn giản đến phứ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 đồng dạng nhưng đơn giản hơn. 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ả. + = Phương pháp lập trình - Đệ quy S(0) + 1 S(0) = 0 Khái niệm đệ quy Khái niệm Vấ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 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. Phương pháp lập trình - Đệ quy Hà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ếp Phương pháp lập trình - Đệ .