Question

Consider the following C function foo(int n). How many times does foo(2) get called on making the call foo(5)?
C Function:

float foo(int n){
    if(n <= 2) return 1;
    else return (2*foo(n-1) + 3*foo(n-2));
}

• A. 4
• B. 3
• C. 2
• D. 1

Hint:

To count recursive calls, always draw or expand the recursion tree and count the required base calls carefully.

Answer 1

The Correct Option is B

Step 1: Understand the recursive calls.
The function \( \texttt{foo}(n) \) makes recursive calls only when \( n > 2 \). For \( n \leq 2 \), the function simply returns 1 without making further calls.
Step 2: Expand the call \( \texttt{foo}(5) \).
\[ \texttt{foo}(5) = 2\cdot \texttt{foo}(4) + 3\cdot \texttt{foo}(3) \]
Step 3: Expand \( \texttt{foo}(4) \) and \( \texttt{foo}(3) \).
\[ \texttt{foo}(4) = 2\cdot \texttt{foo}(3) + 3\cdot \texttt{foo}(2) \] \[ \texttt{foo}(3) = 2\cdot \texttt{foo}(2) + 3\cdot \texttt{foo}(1) \]
Step 4: Count the number of times \( \texttt{foo}(2) \) is called.
From the expansions above:
- One call to \( \texttt{foo}(2) \) comes from \( \texttt{foo}(4) \)
- One call to \( \texttt{foo}(2) \) comes from \( \texttt{foo}(3) \) inside \( \texttt{foo}(5) \)
- One call to \( \texttt{foo}(2) \) comes from \( \texttt{foo}(3) \) inside \( \texttt{foo}(4) \)
Total number of calls to \( \texttt{foo}(2) \) = \( 3 \)
Step 5: Final conclusion.
Therefore, when \( \texttt{foo}(5) \) is executed, the function \( \texttt{foo}(2) \) is called exactly 3 times.

Answer 2

Instead of expanding the entire call tree and counting the foo(2) nodes by hand, we can define a helper count function c(n) equal to the number of times foo(2) gets called while evaluating foo(n), and work out a recurrence for c(n) itself.

By inspecting the code, foo(n) for n>2 makes exactly two recursive calls, to foo(n-1) and foo(n-2); any call to foo(2) that happens during the evaluation of foo(n) must come from inside one of those two recursive branches, plus one extra count if n itself equals 2 (since then the call to foo(n) is itself a call to foo(2)). This gives:

\[ c(n) = c(n-1) + c(n-2) + [n=2], \qquad c(1)=0 \]

Building up from the smallest cases:

\[ c(1) = 0, \quad c(2) = 1, \quad c(3) = c(2)+c(1) = 1, \quad c(4) = c(3)+c(2) = 2, \quad c(5) = c(4)+c(3) = 2+1 = 3 \]

1. 4: The recurrence built up above gives c(5)=3, not 4, so this option does not match.
2. 3: This matches the value of c(5) obtained by building up the count recurrence step by step from the base cases.
3. 2: This corresponds instead to c(4), one step earlier in the buildup, not to c(5), so it does not match the question asked.
4. 1: This corresponds instead to c(2) or c(3), much earlier in the buildup, and is too small to be the count for foo(5).

Building the count recurrence up from the base cases confirms foo(2) is called exactly 3 times while evaluating foo(5).

Therefore, the correct answer is 3.