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: foo(5) calls foo(4) and foo(3). List all calls level by level (breadth-first) starting from foo(5).
Step 2: Level 1: foo(4), foo(3). Level 2: foo(4) leads to foo(3) and foo(2); foo(3) leads to foo(2) and foo(1). So level 2 calls are: foo(3), foo(2), foo(2), foo(1).
Step 3: Level 2 already shows foo(2) appearing twice; the remaining foo(3) at level 2 expands one level further to foo(2) and foo(1), contributing one more foo(2) call at level 3.
\[ \text{Total foo(2) calls} = 2 + 1 = \boxed{3} \]

Answer 2

A third way to verify this is to trace every distinct path from the root call foo(5) down to a node labeled foo(2), where each step down either subtracts 1 (the "2 times" branch) or subtracts 2 (the "3 times" branch) from the current argument.

We need every combination of steps of size 1 and 2 that reduces 5 down to exactly 2, without overshooting past 2 (since the recursion stops at n≤2 and does not continue past a node once it is 2 or less):

1. Path 5 to 4 to 2: subtract 1 (5 to 4), then subtract 2 (4 to 2). This path exists as one branch of the tree and lands exactly on foo(2).
2. Path 5 to 3 to 2: subtract 2 (5 to 3), then subtract 1 (3 to 2). This is a different branch of the tree that also lands exactly on foo(2).
3. Path 5 to 4 to 3 to 2: subtract 1 (5 to 4), subtract 1 (4 to 3), then subtract 1 (3 to 2). This is a third, distinct branch that also lands exactly on foo(2).
4. Any other combination (such as 5 to 3 to 1, or continuing past 5 to 4 to 2 since the recursion halts once n≤2) either lands on foo(1) instead of foo(2), or has already been counted as one of the three paths above, so no additional foo(2) node is generated beyond these three.

Listing every distinct root-to-node path that terminates exactly at argument value 2 finds exactly three such paths through the call tree.

Therefore, the correct answer is 3.