in Programming recategorized by
287 views
3 votes
3 votes

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$
in Programming recategorized by
287 views

3 Answers

4 votes
4 votes
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.

2 Comments

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$
2
2

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

1
1
1 vote
1 vote

Answer : A,B,C,D

$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$

 

0 votes
0 votes

$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.

Answer:

Related questions