Giới thiệu về đệ quy

Đệ quy là một kỹ thuật lập trình trong đó một hàm (function) tự gọi chính nó để giải quyết vấn đề. Hãy hình dung như khi bạn nhìn vào hai chiếc gương đặt đối diện nhau: mỗi hình phản chiếu đều chứa một phiên bản nhỏ hơn của cùng một hình ảnh, tạo thành một vòng lặp vô hạn cho đến khi các hình phản chiếu nhỏ đến mức không thể nhìn thấy.

Mọi hàm đệ quy đều cần hai thành phần thiết yếu để hoạt động đúng cách. Trường hợp cơ sở là điều kiện dừng đệ quy, giống như điểm mà những hình ảnh phản chiếu trong gương trở nên quá nhỏ để còn quan trọng. Nếu không có trường hợp cơ sở, hàm sẽ tự gọi chính nó mãi mãi, cuối cùng khiến chương trình gặp sự cố.

Bước đệ quy là nơi hàm gọi chính nó với một phiên bản đã thay đổi của bài toán ban đầu. Mỗi lần hàm gọi chính nó, hàm nên xử lý một phiên bản nhỏ hơn hoặc đơn giản hơn của bài toán, dần tiến đến trường hợp cơ sở.

Hãy tưởng tượng bạn đang tìm chìa khóa trong một chồng giấy tờ. Bạn có thể kiểm tra tờ giấy trên cùng, nếu không thấy chìa khóa ở đó, bạn sẽ làm tương tự với phần giấy tờ còn lại, lúc này ít hơn một tờ. Bạn sẽ tiếp tục lặp lại quá trình này cho đến khi tìm thấy chìa khóa hoặc không còn tờ giấy nào để kiểm tra.

Cách tiếp cận chia một vấn đề lớn thành những vấn đề nhỏ hơn giống hệt nhau giúp đệ quy trở nên hữu ích khi giải một số dạng thử thách lập trình.