CSD201 - Phần 3: Đệ quy

Ứng với CLO3, buổi 11-14. Tương ứng Chương 5 của Goodrich ấn bản 6. Phần ý tưởng nêu hai thành phần bắt buộc của mọi thuật toán đệ quy là trường hợp cơ sở để dừng và bước đệ quy thu nhỏ bài toán, cùng ba ví dụ dẫn nhập là hàm giai thừa, tìm kiếm nhị phân và duyệt hệ thống tệp. Phần phân tích hướng dẫn cách lần theo một hàm đệ quy để xác định kết quả mà không cần chạy chương trình, và cách ước lượng độ phức tạp qua số lời gọi. Phần phân loại phân biệt đệ quy tuyến tính với một lời gọi, đệ quy nhị phân với hai lời gọi như dãy Fibonacci, và đệ quy bội với nhiều nhánh, kèm ví dụ và so sánh. Phần thiết kế đưa ra quy trình xây dựng một thuật toán đệ quy từ bài toán thực tế. Khép lại bằng kỹ thuật khử đệ quy đuôi và bảng so sánh ưu nhược điểm giữa đệ quy và lặp.