Question

Consider the following C function:
int fun(int n){
if (n == 0) return 0;
else return n + fun(n - 1);
}
What does the function fun(4) return?

• A. 4
• B. 10
• C. 24
• D. 16

Hint:

Always identify the Base Case first. If $n=0$ was not handled, this function would lead to an infinite recursion and eventually a "Stack Overflow" error.

Answer 1

The Correct Option is B

Concept:
The given function is a classic example of Linear Recursion. It defines a mathematical relationship: \[ f(n) = n + f(n-1) \text{ for } n > 0 \] \[ f(0) = 0 \text{ (Base Case)} \] This is the recursive definition for the sum of the first $n$ natural numbers.

Step 1: Tracing the "Winding" phase (Stack Growth).
When fun(4) is called, the computer creates a stack frame and pauses to evaluate the next call:
• fun(4) calls 4 + fun(3)
• fun(3) calls 3 + fun(2)
• fun(2) calls 2 + fun(1)
• fun(1) calls 1 + fun(0)
• fun(0) hits the Base Case and returns 0.

Step 2: Tracing the "Unwinding" phase (Result Substitution).
Now, the results are passed back up the recursion tree:
• fun(1) becomes $1 + 0 = \mathbf{1}$
• fun(2) becomes $2 + 1 = \mathbf{3}$
• fun(3) becomes $3 + 3 = \mathbf{6}$
• fun(4) becomes $4 + 6 = \mathbf{10}$

Step 3: Mathematical Verification.
The sum of first $n$ integers is given by $\frac{n(n+1)}{2}$. For $n = 4$: \[ \text{Sum} = \frac{4(4+1)}{2} = \frac{4 \times 5}{2} = \frac{20}{2} = 10. \] Both the recursive trace and the mathematical formula yield the same result.