Question

Consider the recursive functions represented by the following code segment:

int bar(int n){
     if (n == 1) return 0;
     else return 1 + bar(n/2);
}
int foo(int n){
     if (n == 1) return 1;
     else return 1 + foo(bar(n));
}

The smallest positive integer n for which foo(n) returns 5 is ______.

Note: Ignore syntax errors (if any) in the function.

Hint:

Work out what bar(n) computes first (it halves n repeatedly), then trace how many times foo must call bar before reaching the base case n = 1. Build the smallest possible chain backward from 1.

Answer 1

Correct Answer: 65536

Step 1 (Understand bar(n)): bar(1) = 0. For n != 1, bar(n) = 1 + bar(n/2), where n/2 is integer division. Each call halves n and adds 1 to the count, until n becomes 1. So bar(n) equals the number of times n must be integer-divided by 2 to reach 1, which is bar(n) = floor(log2(n)). Check: bar(2)=1, bar(3)=1 (3/2=1), bar(4)=2, bar(5)=bar(6)=bar(7)=2, bar(8)=3.

Step 2 (Understand foo(n)): foo(1) = 1. For n != 1, foo(n) = 1 + foo(bar(n)). So foo repeatedly replaces its argument by bar(argument) until the argument becomes 1, counting 1 for every replacement plus the base case. Define the chain x0 = n, x1 = bar(x0), x2 = bar(x1), ... . If x_k is the first term equal to 1 (with x0, x1, ..., x_(k-1) all not equal to 1), then foo(n) = k + 1.

Step 3 (Translate the requirement): We need foo(n) = 5, i.e. k = 4: starting from n, four applications of bar must be needed before the value first becomes 1.

Step 4 (Minimality rule): Since bar(n) = floor(log2(n)) is non-decreasing in n, for a fixed target value v the smallest n with bar(n) = v is n = 2^v. So the smallest overall n is obtained by building the chain backward from 1, always choosing the smallest possible predecessor at each stage.

Step 5 (Build the minimal chain backward):
m0 = 1 (this is foo(1) = 1, depth 0).
m1 = smallest x != 1 with bar(x) = m0 = 1. bar(x) = 1 for x = 2 or 3, so m1 = 2. Check: foo(2) = 1 + foo(bar(2)) = 1 + foo(1) = 2.
m2 = smallest x with bar(x) = m1 = 2, i.e. x = 2^2 = 4, so m2 = 4. Check: foo(4) = 1 + foo(bar(4)) = 1 + foo(2) = 1 + 2 = 3.
m3 = smallest x with bar(x) = m2 = 4, i.e. x = 2^4 = 16, so m3 = 16. Check: foo(16) = 1 + foo(bar(16)) = 1 + foo(4) = 1 + 3 = 4.
m4 = smallest x with bar(x) = m3 = 16, i.e. x = 2^16 = 65536, so m4 = 65536.

Step 6 (Verify): For n = 65536: bar(65536) = 16 (since 2^16 = 65536), bar(16) = 4, bar(4) = 2, bar(2) = 1. The chain 65536 -> 16 -> 4 -> 2 -> 1 first reaches 1 at the 4th application, so foo(65536) = 4 + 1 = 5, as required. For n = 65535, bar(65535) = 15 (since 2^15 = 32768 <= 65535 < 65536 = 2^16); the chain becomes 65535 -> 15 -> 3 -> 1, reaching 1 in only 3 applications, so foo(65535) = 4, not 5. Since bar is non-decreasing, no n smaller than 65536 can produce a chain of depth 4, so 65536 is indeed the smallest such n.

\[ \boxed{n = 65536} \]