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 ______. (answer in integer)
Note: Ignore syntax errors (if any) in the function.
foo(n) = 5: Recursive Function Analysis
The problem requires finding the smallest positive integer n for which the recursive function $foo(n)$ evaluates to 5. We are given two recursive functions: $bar(n)$ and $foo(n)$.
bar(n) Function Logic
The definition of $bar(n)$ is:
- If $n == 1$, return 0.
- Else, return $1 + bar(n/2)$.
This function essentially counts how many times $n$ can be divided by 2 using integer division until it reaches 1, and adds 1 to this count. This is equivalent to the floor of the base-2 logarithm of $n$.
For any positive integer $n$, $bar(n)$ can be expressed as:
$bar(n) = \lfloor \log_2(n) \rfloor$
foo(n) Function Definition
The definition of $foo(n)$ is:
- If $n == 1$, return 1.
- Else, return $1 + foo(bar(n))$.
foo(n) = 5 Conditions Derivation
We need to determine the smallest positive integer n such that $foo(n) = 5$.
Let's trace the function calls backwards from the desired output:
- $foo(n) = 5$
- Using the recursive step, $1 + foo(bar(n)) = 5$, which simplifies to $foo(bar(n)) = 4$.
- Let $m_1 = bar(n)$. Then, $foo(m_1) = 4$.
- Applying the rule again, $1 + foo(bar(m_1)) = 4$, implying $foo(bar(m_1)) = 3$.
- Let $m_2 = bar(m_1)$. Then, $foo(m_2) = 3$.
- $1 + foo(bar(m_2)) = 3$, which means $foo(bar(m_2)) = 2$.
- Let $m_3 = bar(m_2)$. Then, $foo(m_3) = 2$.
- $1 + foo(bar(m_3)) = 2$, leading to $foo(bar(m_3)) = 1$.
- Let $m_4 = bar(m_3)$. Then, $foo(m_4) = 1$.
According to the base case definition, $foo(1) = 1$. Therefore, we must have $m_4 = 1$.
Smallest n Value Derivation
We now determine the possible values for the intermediate variables, working backwards from $m_4 = 1$ using the relation $bar(x) = \lfloor \log_2(x) \rfloor$:
- Step 1: Determine possible values for $m_3$
We have $bar(m_3) = m_4 = 1$.
This implies $\lfloor \log_2(m_3) \rfloor = 1$.
The inequality $1 \le \log_2(m_3) < 2$ holds, which means $2^1 \le m_3 < 2^2$, or $2 \le m_3 < 4$. The possible integer values for $m_3$ are {2, 3}. - Step 2: Determine possible values for $m_2$
We have $bar(m_2) = m_3$.
- If $m_3 = 2$: $bar(m_2) = 2$, so $\lfloor \log_2(m_2) \rfloor = 2$. This leads to $2^2 \le m_2 < 2^3$, meaning $4 \le m_2 < 8$.
- If $m_3 = 3$: $bar(m_2) = 3$, so $\lfloor \log_2(m_2) \rfloor = 3$. This leads to $2^3 \le m_2 < 2^4$, meaning $8 \le m_2 < 16$.
- Step 3: Find the smallest possible value for $m_1$
We have $bar(m_1) = m_2$.
To find the smallest positive integer n, we must find the smallest possible value for $m_1$. This occurs when $m_2$ is minimized. The minimum value for $m_2$ from the range $[4, 15]$ is 4.
Setting $bar(m_1) = 4$ implies $\lfloor \log_2(m_1) \rfloor = 4$.
This inequality $4 \le \log_2(m_1) < 5$ holds, meaning $2^4 \le m_1 < 2^5$, or $16 \le m_1 < 32$. The smallest possible value for $m_1$ is 16. - Step 4: Find the smallest positive integer $n$
We have $bar(n) = m_1$.
We need the smallest n such that $bar(n) = 16$ (the smallest $m_1$ derived).
$bar(n) = 16$ means $\lfloor \log_2(n) \rfloor = 16$.
This inequality $16 \le \log_2(n) < 17$ holds, meaning $2^{16} \le n < 2^{17}$.
n Final Computation
The smallest positive integer n satisfying $2^{16} \le n < 2^{17}$ is $n = 2^{16}$.
Calculating this value:
$n = 2^{16} = 65536$.
The smallest positive integer n for which $foo(n)$ returns 5 is 65536.
Important Questions from Function Recursion
The process of removing recursion involves replacing recursive function calls with:
#include <stdio.h> int foo(int S[], int size){ if(size == 0) return 0; if(size == 1) return 1; if(S[0] != S[1]) return 1 + foo(S + 1, size - 1); return foo(S + 1, size - 1); } int main(){ int A[] = {0, 1, 2, 2, 2, 0, 0, 1, 1}; printf("%d", foo(A, 9)); return 0; }The value printed by the given C program is _______ . (Answer in integer)
- Consider the following ANSI-C function.
int func(int start, int end){
int length=end+1-start;
if((length < 1)||(start < 0)||(end < 0)){ return(0); }
if(length%3==0){
return(func(start+1, end));
} else if(length%3==1){
return(1+func(start, end-1));
} else {
return(func(start+2, end));
}
}
The maximum possible value that can be returned from this function is ____________. (answer in integer)
Note: Ignore syntax errors (if any) in the function. - What is the value returned by the function f given below when n = 100 ?
int f (int n)
{ if (n == 0) then return n;
else
return n + f(n-2);
} What is the output of the given C language code snippet?
#include<stdio.h>
void f(int n)
{
if(n==0)
return;
printf("%d ",n);
f(n-1);
}
int main()
{
f(3);
return 0;
}
