Consider the following C functions: int f1 (int n) { if(n == 0 || n == 1)…
2008
Consider the following C functions:
int f1 (int n)
{
if(n == 0 || n == 1)
return n;
else
return (2 * f1(n-1) + 3 * f1(n-2));
}
int f2(int n)
{
int i;
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for(i = 2; i <= n; i++){
X[i] = Y[i-1] + Z[i-2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}f1(8) and f2(8) return the values
- A.
1661 and 1640
- B.
59 and 59
- C.
1640 and 1640
- D.
1640 and 1661
Attempted by 18 students.
Show answer & explanation
Correct answer: C
Answer: f1(8) = 1640 and f2(8) = 1640
Key idea: f2's arrays produce the same recurrence and base values as f1, so both functions yield identical results.
Compute f1 step by step using f1(0)=0, f1(1)=1 and f1(n)=2*f1(n-1)+3*f1(n-2): f1(0)=0, f1(1)=1, f1(2)=2, f1(3)=7, f1(4)=20, f1(5)=61, f1(6)=182, f1(7)=547, f1(8)=1640.
Analyze f2: initial values are X[0]=0, X[1]=1, Y[0]=0, Y[1]=2, Z[0]=0, Z[1]=3. The loop sets Y[i]=2*X[i] and Z[i]=3*X[i] for each i, and X[i]=Y[i-1]+Z[i-2]. Substituting gives X[i]=2*X[i-1]+3*X[i-2], the same recurrence as f1.
Since the base values X[0]=0 and X[1]=1 match f1's base cases and the recurrence is identical, X[n]=f1(n) for all n. Therefore X[8]=f1(8)=1640, so f2(8) returns 1640 as well.