What is the value returned by the function f given below when n = 100? let…
2016
What is the value returned by the function f given below when n = 100?
let f(int n)
{
if (n == 0) then return n;
else
return n + f(n - 2);
}- A.
2550
- B.
2556
- C.
5220
- D.
5520
Attempted by 437 students.
Show answer & explanation
Correct answer: A
Concept
A recursive function that returns n + f(n - 2) and stops at the base case f(0) = 0 accumulates the term n at every call and adds the result of the next call. Unrolling the recursion therefore produces an additive chain: the returned value is the sum of n, n-2, n-4, ... down to the base value. Since the step is 2 and the base case is 0, with an even starting argument every term in this chain is even.
Application
Trace the recursion for n = 100:
f(100) = 100 + f(98); the call does not stop because 100 is not 0, so it adds 100 and recurses on 98.
Each subsequent call subtracts 2 and adds its own argument: f(98) = 98 + f(96), f(96) = 96 + f(94), and so on.
The chain reaches f(0), the base case, which returns 0 and ends the recursion.
Substituting back, the total returned is 100 + 98 + 96 + ... + 4 + 2 + 0.
Factor out 2 from every term: 2 x (50 + 49 + ... + 1) = 2 x (1 + 2 + ... + 50).
Use the sum of the first 50 natural numbers: 1 + 2 + ... + 50 = 50 x 51 / 2 = 1275.
Therefore the value is 2 x 1275 = 2550.
Cross-check
The chain 0, 2, 4, ..., 100 is an arithmetic progression with first term 0, last term 100 and 51 terms. Its sum is (number of terms) x (first + last) / 2 = 51 x (0 + 100) / 2 = 51 x 50 = 2550, which matches the recursive computation. So the function returns 2550 when n = 100.