Trace tổng đệ quy

Bối cảnh

Một công cụ học tập muốn hiển thị thứ tự các frame xuất hiện khi tính tổng từ 1 đến n bằng đệ quy.

Để nhìn rõ CALL và RETURN, bạn sẽ in n khi đi xuống và in kết quả từng tầng khi đi ngược lên.

Yêu cầu

1. Viết hàm đệ quy traceSum(n) với base case n=0.
2. Trước khi gọi tầng dưới, in CALL n.
3. Sau khi nhận kết quả tầng dưới, tính kết quả hiện tại và in RETURN n result.
4. Cuối cùng in ANSWER x.

Yêu cầu tổ chức code

Phải dùng recursion để tạo trace; không mô phỏng toàn bộ bằng vòng lặp.

Online Judge chủ yếu chấm output. Giảng viên sẽ quan sát thêm cách tổ chức hàm khi review code để bảo đảm học viên luyện đúng kỹ năng của buổi.

Input

Một số nguyên n.

Output

Các dòng trace đúng thứ tự, kết thúc bằng ANSWER.

Ràng buộc

0 ≤ n ≤ 12.

Ví dụ 1

Input

3

Output

CALL 3
CALL 2
CALL 1
CALL 0
RETURN 0 0
RETURN 1 1
RETURN 2 3
RETURN 3 6
ANSWER 6

Giải thích

Call stack đi 3 → 2 → 1 → 0. Khi chạm base case, kết quả 0 quay lên và lần lượt tạo 1, 3, 6.

Ví dụ 2

Input

0

Output

CALL 0
RETURN 0 0
ANSWER 0

Giải thích

Với n=0, lời gọi đầu tiên đã là base case nên chỉ có CALL 0, RETURN 0 0, rồi ANSWER 0.

Thông tin học tập

• Module: M04
• Buổi: B13
• Loại bài: LAB
• Độ khó: Easy
• Concepts: recursion, base case, recursive case, call stack, return flow
• Giới hạn kiến thức: B01-B13
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100