Cấu trúc của chương trình con đệ quy gồm.

Một chương trình con đệ quy bao gồm hai phần chính: * **Phần cơ sở (Base case):** Đây là trường hợp đơn giản nhất mà chương trình con có thể giải quyết trực tiếp mà không cần gọi lại chính nó. Phần cơ sở đóng vai trò là điểm dừng cho quá trình đệ quy, ngăn chặn việc chương trình con gọi lại chính nó vô hạn lần. * **Phần đệ quy (Recursive case):** Đây là phần mà chương trình con gọi lại chính nó để giải quyết một phiên bản nhỏ hơn của vấn đề ban đầu. Phần đệ quy phải đảm bảo rằng mỗi lần gọi lại chính nó, vấn đề trở nên đơn giản hơn và tiến gần hơn đến phần cơ sở. Các phương án khác không mô tả chính xác cấu trúc của một chương trình con đệ quy. Phần 'dễ giải quyết' và 'khó giải quyết' không phải là thuật ngữ chính thức. 'Phần quy nạp' thường được sử dụng trong chứng minh toán học hơn là mô tả cấu trúc chương trình. 'Phần hữu hạn' không liên quan đến cấu trúc của đệ quy.