Bài giảng Nhập môn lập trình: Đệ quy (recursion) - Trường ĐH Công nghệ thông tin

Tài liệu này giới thiệu về khái niệm đệ quy trong lập trình, một kỹ thuật mạnh mẽ cho phép giải quyết các vấn đề phức tạp bằng cách chia nhỏ chúng thành các bài toán con tương tự. Chúng ta sẽ khám phá các loại đệ quy khác nhau và cách chúng hoạt động.

Sinh viên và nhà nghiên cứu trong lĩnh vực khoa học máy tính và các ngành liên quan, những người muốn hiểu và áp dụng kỹ thuật đệ quy trong lập trình.

Tài liệu này trình bày một cách toàn diện về đệ quy, bắt đầu với định nghĩa cơ bản về đệ quy và cách nó được sử dụng để giải quyết các vấn đề bằng cách tự gọi lại với các đầu vào đơn giản hơn. Các ví dụ minh họa như tính giai thừa và tổng các số tự nhiên được sử dụng để làm rõ khái niệm. Tài liệu cũng giới thiệu về trường hợp cơ bản (base case), là điều kiện dừng cho các lời gọi đệ quy. Sau đó, tài liệu đi sâu vào việc triển khai đệ quy trong C++, minh họa cách một hàm có thể gọi lại chính nó. Các loại đệ quy khác nhau, bao gồm đệ quy tuyến tính (single recursion), đệ quy phi tuyến (multiple recursion) và đệ quy hỗ tương (mutual recursion), được giải thích chi tiết. Đệ quy tuyến tính, trong đó hàm chỉ gọi lại chính nó một lần, được so sánh với các giải pháp lặp tương đương, nhấn mạnh rằng các vòng lặp thường nhanh hơn và hiệu quả hơn về mặt bộ nhớ. Đệ quy phi tuyến, được minh họa bằng dãy Fibonacci, trong đó hàm gọi lại chính nó nhiều lần, được thảo luận cùng với những thách thức trong việc chuyển đổi nó thành cấu trúc lặp. Cuối cùng, tài liệu giải thích khái niệm về call stack và cách mỗi lời gọi hàm tạo ra một phần tử mới trong stack. Tầm quan trọng của việc quản lý call stack để tránh tràn stack (stack overflow) cũng được nhấn mạnh.