ITPEC FE Subject A October 2024 Question 6

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 — 5², 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