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.