tailieunhanh - Bài giảng Hệ thống máy tính và ngôn ngữ lập trình - Chương 14: Đệ quy

Bài giảng Hệ thống máy tính và ngôn ngữ lập trình - Chương 14: Đệ quy. Bài giảng cung cấp cho học viên những kiến thức về khái niệm đệ quy; đệ quy và lặp; tháp Hà nội; dãy số Fibonacci; tìm kiếm nhị phân; chuyển số nguyên sang dãy ký tự ASCII; cấu trúc dữ liệu cây – cây nhị phân; . Mời các bạn cùng tham khảo! | 1 Các nội dung Đệ quy là gì Đệ quy và lặp Tháp Hà nội Dãy số Fibonacci Tìm kiếm nhị phân Chuyển số nguyên sang dãy ký tự ASCII Cấu trúc dữ liệu cây cây nhị phân TS. Nguyễn Phúc Khải 2 Đệ quy là gì n Ví dụ Tính tổng i 1 int RunningSum int n if n 1 return 1 else return n RunningSum n-1 TS. Nguyễn Phúc Khải 3 ĐỆ QUY VÀ LẶP Tất cả các hàm đệ quy đều có thể được viết bằng vòng lặp. Việc sử dụng đệ quy sẽ dễ dàng và trong sáng hơn khi dùng vòng lặp. Bản đệ quy tương đối chậm vì các hàm đệ quy chịu sự gọi hàm còn vòng lặp thì không. TS. Nguyễn Phúc Khải 4 THÁP HÀ NỘI Bài toán một nền có ba cột một trong ba cột có các đĩa gỗ sắp theo thứ tự đĩa nhỏ ở trên đĩa lớn ở dưới. Chúng ta phải chuyển tất cả các đĩa từ cột hiện thời qua một trong hai cột kia theo hai luật sau mỗi lần chỉ được di chuyển một đĩa và đĩa lớn không được đặt trên đĩa nhỏ. TS. Nguyễn Phúc Khải 5 DÃY SỐ FIBONACCI Ta có phương trình toán truy hồi sau f n f n - 1 f n - 2 f 1 1 f 0 1 hàm đệ quy để tính số Fibonacci thứ n là phương trình truy hồi trên. TS. Nguyễn Phúc Khải 6 CÁC BÀI TOÁN Tìm kiếm nhị phân Chuyển số nguyên sang chuỗi ký tự ASCII TS. Nguyễn Phúc Khải 7 TS. Nguyễn Phúc Khải 8