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!
Nội dung trích xuất từ tài liệu:
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 KỸ THUẬT ĐỆ QUY (RECURSION) Khoa Công nghệ thông tinTrường Đại học Ngoại ngữ - Tin học TP.HCM (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 2KHÁI NIỆM ĐỆ QUYKhá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 ∗ ⋯∗ ? ?ế? ? > 0 ? ∗ ?− ? ! ?ế? ? > 0 4Khái niệm Đệ quy• Ví dụ 2: Hãy tính f(1), f(2), f(3) với 1 ?ế? ? = 0 ? ? =൦ 1 ? ?−1 + ?ế? ? > 0 ?(? − 1)• Ví dụ 3: Hãy tính f(3), f(4), f(5), f(6) với 1 ?ế? ? = 1 ℎ?? ? = 2 ? ? =ቈ ? ? − 1 + ?(? − 2) ?ế? ? > 2 5Khá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. 6Khá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) ?ế? ? > 2 Điều Thành phần đệ quy kiện đệ quy 7Khá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 8Khá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 ? ?ế? ? = 0USCLN(A, B) = ቈ ?????(?, ? ??? ?) ?ế? ? ≠ 0 9Khá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 10KỸ THUẬT CÀI ĐẶT HÀM ĐỆ QUYThiết kế thuật giải đệ quy• 3 bước thiết kế thuật giải đệ quy: • Tham số hóa bài toán. • Phân tích trường hợp chung: đưa bài toán về bài toán nhỏ hơn cùng loại, dần dần tiến tới trường hợp suy biến. • Tìm trường hợp suy biến. 12Một số dạng đệ quy• Đệ quy tuyến tính (Linear Recursion): mỗi lần thực thi chỉ gọi đệ quy một lần. • Ví dụ: Bài toán tính giai thừa, Dãy Fibonaci. int Factorial(int n) { if (n == 0) { return 1; } else { // Linear Recursion return n * Factorial(n - 1); } } 13Một số dạng đệ quy• Đệ quy nhị phân (Binary Recursion): mỗi lần thực thi có thể gọi đệ quy 2 lần.• Ví dụ: Bài toán tháp Hà Nội, Tính tổ hợp ch ...