Trong bất cứ hàm đệ qui nào cũng phải có điều kiện dừng, điều kiện này sẽ kết thúc quá trình đệ qui bằng một đoạn mã chương trình được viết theo lối thông thường. Tập tin là một loại dữ liệu có thể ghi lên đĩa để dùng nhiều lần. Có 2 loại tập tin: Tập tin văn bản (text file, ASCII file): *.PAS, *.C, (các tập tin mã nguồn chương trình). Mỗi tập tin văn bản gồm nhiều dòng. Mã ngăn cách dòng (chuyển dòng khác) là mã 10 ($OA), được tách ra thành mã 13 ($OD) và mã 10. | TIN HỌC ĐẠI CƯƠNG BÀI 11 ĐỆ QUY TẬP TIN ĐỆ QUY 11 NỘI DUNG Khái niệm Phân loại các hàm đệ qui: Đệ qui tuyến tính Đệ qui nhị phân Đệ qui hỗ tương Đệ qui phi tuyến NỘI DUNG BÀI ĐỆ QUY Trong bất cứ hàm đệ qui nào cũng phải có điều kiện dừng, điều kiện này sẽ kết thúc quá trình đệ qui bằng một đoạn mã chương trình được viết theo lối thông thường. Ví dụ: if (N==1) return 1; ĐIỀU KIỆN DỪNG Đệ qui Lặp Sử dụng cấu trúc lựa chọn Sử dụng cấu trúc lặp Sử dụng liên tục các lời gọi hàm Sử dụng vòng lặp tường minh Kết thúc khi đến trường hợp cơ sở Kết thúc khi điều kiện để tiếp tục vòng lặp sai Làm cho các lời gọi hàm đơn giản dần cho đến khi tới trường hợp cơ sở Thay đổi biến đếm trong vòng lặp cho đến khi nó làm cho điều kiện lặp sai Không thoát ra được khi các bước đệ qui không làm cho bài toán đơn giản hơn và cuối cùng hội tụ về trường hợp cơ sở Lặp sẽ không thoát ra được khi điều kiện lặp không bao giờ sai Đệ qui tồi hơn, nó liên tục đưa ra các lời gọi hàm làm tốn thời gian xử lý và không gian nhớ. Mỗi lần gọi hàm, lại cần thêm một bản sao của hàm, tốn thêm bộ nhớ (lưu các biến của hàm, địa chỉ trở về của hàm .). Phương pháp lặp được chuộng hơn Tuy nhiên, có nhiều bài toán có thể giải bằng đệ qui lại tốt hơn (các bài toán cổ điển: tháp Hà Nội, mã đi tuần, 8 hậu, sắp xếp QuickSort ) SO SÁNH ĐỆ QUY VÀ LẶP Đệ qui tuyến tính Đệ qui nhị phân Đệ qui hỗ tương Đệ qui phi tuyến PHÂN LOẠI CÁC DẠNG ĐỆ QUY Một hàm được gọi là đệ qui tuyến tính khi nó có dạng: { if { /*Trả về giá trị hay kết thúc công việc.*/ } else { /*Làm một số công việc.*/ /*Gọi đệ qui đến hàm */ } } ĐỆ QUY TUYẾN TÍNH Viết hàm đệ qui tính xn, n nguyên dương. Điều kiện dừng: nếu n=0 thì x0=1. Tổng quát: xn=xn-1*x. float xn(float x, int n) { if (n==0) return 1; else return xn(x,n-1)*x; } VÍ DỤ VỀ ĐỆ QUY TUYẾN TÍNH Một hàm được gọi là đệ qui nhị phân khi nó có dạng: { if /*Trả về gtrị hay kthúc công việc.*/ else { . | TIN HỌC ĐẠI CƯƠNG BÀI 11 ĐỆ QUY TẬP TIN ĐỆ QUY 11 NỘI DUNG Khái niệm Phân loại các hàm đệ qui: Đệ qui tuyến tính Đệ qui nhị phân Đệ qui hỗ tương Đệ qui phi tuyến NỘI DUNG BÀI ĐỆ QUY Trong bất cứ hàm đệ qui nào cũng phải có điều kiện dừng, điều kiện này sẽ kết thúc quá trình đệ qui bằng một đoạn mã chương trình được viết theo lối thông thường. Ví dụ: if (N==1) return 1; ĐIỀU KIỆN DỪNG Đệ qui Lặp Sử dụng cấu trúc lựa chọn Sử dụng cấu trúc lặp Sử dụng liên tục các lời gọi hàm Sử dụng vòng lặp tường minh Kết thúc khi đến trường hợp cơ sở Kết thúc khi điều kiện để tiếp tục vòng lặp sai Làm cho các lời gọi hàm đơn giản dần cho đến khi tới trường hợp cơ sở Thay đổi biến đếm trong vòng lặp cho đến khi nó làm cho điều kiện lặp sai Không thoát ra được khi các bước đệ qui không làm cho bài toán đơn giản hơn và cuối cùng hội tụ về trường hợp cơ sở Lặp sẽ không thoát ra được khi điều kiện lặp không bao giờ sai Đệ qui tồi hơn, nó liên tục đưa ra các lời gọi hàm làm tốn thời gian xử .
