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 (Alternate method - build the ranges of n for each foo value directly): As shown above, bar(n) = floor(log2(n)). Instead of working backward from a single minimal chain, find the complete interval of n that produces each value of foo, then read off where foo first becomes 5.

Step 2: foo(n) = 1 exactly for n = 1.

Step 3: foo(n) = 2 requires bar(n) to land in the foo = 1 set, i.e. bar(n) = 1, i.e. floor(log2(n)) = 1, i.e. n in [2, 3].

Step 4: foo(n) = 3 requires bar(n) in the foo = 2 range [2, 3]. floor(log2(n)) in [2, 3] covers n in [4, 7] (value 2) union n in [8, 15] (value 3), giving n in [4, 15].

Step 5: foo(n) = 4 requires bar(n) in the foo = 3 range [4, 15]. floor(log2(n)) taking every value from 4 to 15 covers n in [16, 31], [32, 63], ..., [32768, 65535], whose union is n in [16, 65535].

Step 6: foo(n) = 5 requires bar(n) in the foo = 4 range [16, 65535]. floor(log2(n)) = 16 first occurs at n = 65536 (2^16 = 65536), so the foo = 5 range begins exactly at n = 65536.

Step 7: The smallest n in this range is n = 65536, confirming the earlier chain-based derivation.

\[ \boxed{n = 65536} \]