tailieunhanh - Bài giảng Kỹ thuật lập trình: Chương 6 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

Bài giảng Kỹ thuật lập trình: Chương 6 Kỹ thuật đệ quy, cung cấp cho người đọc những kiến thức như: Khái niệm Đệ quy; Kỹ thuật cài đặt Hàm đệ quy; Cơ chế hoạt động của Hàm đệ quy. Mời các bạn cùng tham khảo! | KỸ THUẬT ĐỆ QUY RECURSION Khoa Công nghệ thông tin Trường Đại học Ngoại ngữ - Tin học HUFLIT Nội dung Khái niệm Đệ quy Kỹ thuật cài đặt Hàm đệ quy Cơ chế hoạt động của Hàm đệ quy Bài tập vận dụng 2 KHÁI NIỆM ĐỆ QUY Khái niệm Đệ quy Một hàm toán học có thể được định nghĩa Thông qua công thức toán học tường minh Thông qua chính hàm đang muốn định nghĩa định nghĩa theo cách đệ quy Ví dụ 1 Định nghĩa hàm n n giai thừa 1 ế 0 ቈ 1 ế 0 ቈ 1 2 ế gt 0 ế gt 0 4 Khái niệm Đệ quy Ví dụ 2 Hãy tính f 1 f 2 f 3 với 1 ế 0 ൦ 1 1 ế gt 0 1 Ví dụ 3 Hãy tính f 3 f 4 f 5 f 6 với 1 ế 1 ℎ 2 ቈ 1 2 ế gt 2 5 Khái niệm Đệ quy Một đối tượng được gọi là đệ quy nếu nó được định nghĩa thông qua chính nó hoặc một đối tượng khác cùng dạng với nó bằng quy nạp. Bài toán đệ quy là bài toán có thể được phân rã thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn nữa. Cứ tiếp tục như thế cho đến khi không thể chia nhỏ được hoặc đạt được kết quả mong muốn. 6 Khái niệm Đệ quy Các thành phần của một hàm đệ quy Thành phần không đệ quy phần neo Điều kiện thoát khỏi đệ quy gọi là trường hợp suy biến. Chứa quy tắc công thức để tính ngay giá trị của hàm số. Thành phần đệ quy công thức đệ quy Thân hàm có chứa lời gọi đệ quy. Điều Thành phần không đệ quy kiện dừng 1 ế 1 ℎ 2 ቈ 1 2 ế gt 2 Điều Thành phần đệ quy kiện đệ quy 7 Khái niệm Đệ quy Nhận xét Khi thực hiện tính toán hàm đệ quy Thường chúng ta xuất phát từ Thành phần đệ quy Quá trình tính toán sẽ lặp đi lặp lại theo công thức đệ quy và quá trình tính toán này phải tiến về Thành phần không đệ quy 8 Khái niệm Đệ quy Ví dụ Mô tả hàm đệ quy tính USCLN A B . Minh họa quá trình thực hiện với 1 A 126 và B 72 2 A 72 và B 126 ế 0 USCLN A B ቈ ế 0 9 Khái niệm Đệ quy ế 0 USCLN A B ቈ ế 0 Minh họa 1 USCLN 126 72 USCLN 72 54 B 72 0 USCLN 54 18 B 54 0 USCLN 18 0 B 18 0 18 B 0 Minh họa 2 USCLN 72 126 USCLN 126 72 B 126 0 USCLN 72 54 B 72 0 USCLN 54 18 B 54 0 USCLN 18 0 B 18 0 18 B 0 10 KỸ