Tinhọcđạicương - bài 11: đệ quy tập tin

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...
Nội dung trích xuất từ tài liệu:
Tinhọcđạicương - bài 11: đệ quy tập tinwww.uit.edu.vn TINHỌCĐẠICƯƠNG BÀI 11 ĐỆ QUY TẬP TIN 1 NỘI DUNG 11 ĐỆ QUYTinhọcđạicương 2 NỘI DUNG BÀI ĐỆ QUY 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ếnTinhọcđạicương 3 ĐIỀU KIỆN DỪNG 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;Tinhọcđạicương 4 SO SÁNH ĐỆ QUY VÀ LẶP Đệ 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 Thay đổi biến đếm trong vòng đến khi tới trường hợp cơ sở 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 Lặp sẽ không thoát ra được không làm cho bài toán đơn giản hơn và khi điều kiện lặp không bao cuối cùng hội tụ về trường hợp cơ sở giờ sai Đệ qui tồi hơn, nó liên tục đưa ra các lời gọi Phương pháp lặp được hàm làm tốn thời gian xử lý và không gian chuộng hơn 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 ...).Tinhọcđạicương 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…) 5 PHÂN LOẠI CÁC DẠNG ĐỆ QUY Đệ qui tuyến tính Đệ qui nhị phân Đệ qui hỗ tương Đệ qui phi tuyếnTinhọcđạicương 6 ĐỆ QUY TUYẾN TÍNH Một hàm được gọi là đệ qui tuyến tính khi nó có dạng: < tên hàm> { if < điều kiện dừng > { /*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 */Tinhọcđạicương } } 7 VÍ DỤ VỀ ĐỆ 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;Tinhọcđạicương } 8 ĐỆ QUY NHỊ PHÂN Một hàm được gọi là đệ qui nhị phân khi nó có dạng: < tênhàm> { if < điều kiện dừng > /*Trả về gtrị hay kthúc công việc...*/ else { /*Làm một số công việc ...*/ /*Gọi đqui đến để giải quyết vấn đề nhỏ hơn */ /*Gọi đqui đến đểTinhọcđạicương giải quyết vấn đề còn lại */ } } 9 VÍ DỤ VỀ ĐỆ QUY NHỊ PHÂN Viết hàm đệ qui tính số hạng thứ n của dãy fibo. F0=F1=1 Fn=Fn-1+Fn-2 Điều kiện dừng: nếu n=0 hay n=1 thì Fn=1. long fibo(int n) { if ((n==0)||(n==1)) return 1; elseTinhọcđạicương return (fibo(n-1)+fibo(n-2)); } 10 ĐỆ QUY PHI TUYẾN Một hàm được gọi là đệ qui phi tuyến khi nó có dạng: ...