ITPEC FE Morning April 2018 Question 7
Function F(n) is a recursively defined integer function that calculates the factorial of n for any non-negative integer n. Which of the following is an appropriate expression for the blank A?
F(0) = 1
F(n) = A (if n > 0)
Explanation
n × F(n − 1) — n! = n × (n − 1)!, and the recursive call on n − 1 moves toward the base case F(0) = 1.
Check with n = 3: F(3) = 3 × F(2) = 3 × 2 × F(1) = 3 × 2 × 1 × F(0) = 3 × 2 × 1 × 1 = 6, which is 3!.
A recursive definition needs two things: a base case that stops the recursion, and a recursive case that calls the function on a smaller argument.
Answer (c)
Why not others:
- •(a) — adds instead of multiplying: F(3) = 3 + 2 + 1 + 1 = 7, a sum, not 3! = 6
- •(b) — calls F(n) inside the definition of F(n); the argument never shrinks, so the recursion never reaches F(0)
- •(d) — also calls F(n) on the same argument, so it never ends, and the factor n − 1 is wrong as well
Key rule: In a recursive definition, each call must work on a smaller argument that eventually reaches the base case; a call with the same argument recurses forever.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.