Consider the following function foo()
void foo(int n)
{
if(n<=0) printf("Bye");
else
{
printf("Hi");
foo(n-3);
printf("Hi");
foo(n-1);
}
}
Let P(n) represent the recurrence relation indicating the number of times the print statement (both “Hi” and “Bye” included) is executed. Then which of the following is the best match for P(n)?
- $\text{P(n)=P(n-1)+P(n-3)+2 for n>=0;1 for n=0}$
- $\text{P(n)=P(n-1)+P(n-3)+2 for n>0;2 for n=0}$
- $\text{P(n)=P(n-1)+P(n-3)+2 for n>0;0 for n=0}$
- $\text{P(n)=P(n-1)+P(n-3)+1 for n>0;2 for n=0}$
Ans. A
But when n=1, the o/p will be “Hi Bye Hi Bye” i.e 4 times printed.
From A, P(1)=P(0)+P(-2)+2 = 1+P(-2)+2=3+P(-2)
But nothing is mentioned about P value when n<0.
How to solve for P(-2) and other negative values?