IPA FE Subject A sample Question 8
A question IPA Japan published in 基本情報技術者試験 科目A サンプル問題 問8, translated into English. ITPEC is based on the same exams.
Same question on ITPEC: Oct 2024 Q6
The function f(n) is recursively defined in terms of the natural number n as below. Which of the following is the value of f(5)?
f(n): if n≦1 then return 1 else return n + f(n−1)
Explanation
15 — the recursion adds n to f(n − 1) until the base case f(1) = 1, so f(5) = 5 + 4 + 3 + 2 + 1.
- •f(1) = 1 (base case, since 1 ≦ 1)
- •f(2) = 2 + f(1) = 3
- •f(3) = 3 + f(2) = 6
- •f(4) = 4 + f(3) = 10
- •f(5) = 5 + f(4) = 15
This is the triangular number n(n + 1) ÷ 2 = 5 × 6 ÷ 2 = 15.
Answer (c)
Why not others:
- •(a) 6 — that is f(3), the recursion stopped two levels early
- •(b) 9 — 5 + 4: uses n − 1 itself in place of the recursive call f(n − 1)
- •(d) 25 — 52, multiplying instead of summing 5 down to 1
Key rule: Trace a recursive definition upward from the base case and tabulate each value; f(n) = n + f(n − 1) with f(1) = 1 is the sum 1 + 2 + … + n.
Algorithm and Programming · AI-written, may contain errors
This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.