Phương pháp thiết kế một giải thuật đệ quy: Tham số hoá bài toán. Phân tích trường hợp chung : đưa bài toán dưới dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến trường hợp suy biến. Tìm trường hợp suy biến. | Chương 2: ĐỆ QUY (Recursion) Ngôn ngữ lập trình C++ NộI DUNG Đệ quy (recursion) Các loại đệ quy (types of recursion) Phương pháp thiết kế một giải thuật đệ quy: Tham số hoá bài toán Phân tích trường hợp chung : đưa bài toán dưới dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến trường hợp suy biến Tìm trường hợp suy biến 1. Đệ quy (Recursion) 1. Đệ quy (Recursion) Chương trình đệ quy gồm hai phần chính: Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm dừng) Phần đệ quy: Trong phần thân chương trình có lời gọi đến chính bản thân chương trình với giá trị mới của tham số nhỏ hơn giá trị ban đầu Ví dụ 1 : Lập hàm tính n! bằng đệ quy int GT(int n) { if (n==0) // điểm dừng return 1; else return n*GT(n-1); } 1. Đệ quy (Recursion) – 1. Đệ quy (Recursion) Gọi hàm answer 1. Đệ quy (Recursion) CT chính: Chưa xong: answer 1. Đệ quy (Recursion) CT chính: Chưa xong: answer 1. Đệ quy (Recursion) CT chính: Chưa xong: answer 1. Đệ quy (Recursion) CT chính: Chưa xong: answer 1. Đệ quy (Recursion) CT chính: Chưa xong: answer 1. Đệ quy (Recursion) CT chính: Chưa xong: answer NộI DUNG Đệ quy (recursion) Các loại đệ quy (types of recursion) Phương pháp thiết kế một giải thuật đệ quy: Tham số hoá bài toán Phân tích trường hợp chung : đưa bài toán dưới dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghiã dần dần sẽ tiến đến trường hợp suy biến Tìm trường hợp suy biến 1. Đệ quy (Recursion) 1. Đệ quy (Recursion) Chương trình đệ quy gồm hai phần chính: Phần cơ sở: Điều kiện thoát khỏi đệ quy (điểm dừng) Phần đệ quy: Trong phần thân chương trình có lời gọi đến chính bản thân chương trình với giá trị mới của tham số nhỏ hơn giá trị ban đầu Ví dụ 1 : Lập hàm tính n! bằng đệ quy int GT(int n) { if (n==0) // điểm dừng return 1; else return n*GT(n-1); } 1. Đệ quy (Recursion) – 1. Đệ quy (Recursion) Gọi hàm answer 1. Đệ quy (Recursion) CT chính: Chưa xong: answer <- GT(5) GT. 1st: N=5, Chưa xong: 5*GT(4) .
