287 views

Consider the following pair of mutually recursive functions.

int f(int n){
if (n==0) return 1;
return f(n-1)+g(n-1);
}
int g(int n){
if (n==0) return 1;
return g(n-1) - f(n);
}


Which of the following is/are will evaluate to TRUE?

1. $f(2) == g(0)$
2. $g(2)+f(1) == 0$
3. $g(4)+g(1) == 0$
4. $f(3)+f(0) == 0$

We can write ,

$f(n)=f(n-1)+g(n-1)$ , ………..(1)

$f(0)=1$

$g(0)=1$

$f(1)=f(0)+g(0)=1+1=2$

$g(n)=g(n-1)-f(n)$ ,  $g(0)=1$

$g(n)=g(n-1)-f(n)$

$g(n)=f(n)-f(n-1)-f(n)$      [as ,from (1) we get $g(n-1)=f(n)-f(n-1)$]

$g(n)=-f(n-1)$ ; $n\geq 1$

$g(n-1)=-f(n-2)$ ; ………….(2)

Putting this in (1) we get ,

$f(n)=f(n-1)-f(n-2)$ $n\geq 2$

$f(0)=1$, $f(1)=2$

$f(2)=f(1)-f(0)=2-1=1$

$f(3)=f(2)-f(1)=1-2=-1$

$g(1)=-f(0)=-1$

$g(2)=-f(1)=-2$

$g(3)=-f(2)=-1$

$g(4)=-f(3)=1$

Now if you checked all the option are correct.

From options, it is clear that, we need recurrence for $f$ in $g,$ $g$ in $f,$ $f$ in $g$ and $f$ in $f.$

As you have represented $g$ in $f$ in equation $(2)$ we can do it for all above as:

$f(n) = f(n-1) + g(n-1), \ n\geq 1$ $\ \ (1)$

$g(n) = g(n-1) - f(n), \ n\geq 1 \implies g(n-1) = g(n-2) - f(n-1)$

Putting this $g(n-1) = g(n-2) - f(n-1)$ in equation $(1),$ we get,

$f(n) = f(n-1) + g(n-2) - f(n-1)$

So, $f(n) = g(n-2); \ \ n \geq 2$ $\ \ (2)$

Since, you have already proved that $g(n) = -f(n-1) \implies g(n-2) = -f(n-3)$

Now, putting $g(n-2) = -f(n-3)$ in equation $(2),$ we get,

$f(n)= -f(n-3)$ $\ \ (3)$

Since, you have already proved that $g(n) = -f(n-1)$ and since, from equation $(2), f(n-1) = g(n-3)$

So, $g(n) =\ – g(n-3)$

So, our recurrences are:

1. $f(n) = g(n-2);\ n\geq 2$
2. $g(n) = -f(n-1) ; n \geq 1$
3. $f(n) = -f(n-3); \ n\geq 3$
4. $g(n) = -g(n-3); \ n \geq 3$

@ankitgupta.1729 yes its nice to play with this equation .

$f(0) = 1$

$g(0) = 1$

$f(1) = f(0)+g(0) = 2$

$g(1) = g(0)-f(1) = 1-2 = -1$

$f(2) = f(1)+g(1) = 2-1 = 1$

$g(2) = g(1)-f(2) = -1-1 = -2$

$f(3) = f(2)+g(2) = 1-2 = -1$

$g(3) = g(2)-f(3) = -2+1 = -1$

$f(4) = f(3)+g(3) = -1-1 = -2$

$g(4) = g(3)-f(4) = -1 + 2 = 1$

1. $f(2) == g(0)$ $TRUE$
2. $g(2) + f(1) = -2+2 = 0$ $TRUE$
3. $g(4) + g(1) = 1-1 = 0$ $TRUE$
4. $f(3) + f(0) = -1+1 = 0$ $TRUE$

$f(0) = 1$;   $g(0) = 1$.

$f(1) = 2$;   $g(1) = -1$.

$f(2) = 1$;   $g(2) = -2$.

$f(3) = -1$;   $g(3) = -1$.

$f(4) = -2$;   $g(4) = 1$.

Answer : – A, B, C, D.