edited by
829 views
5 votes
5 votes

Consider the following pair of mutually recursive functions. What does $g(g(2))$ evaluate to?

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

3 Answers

Best answer
9 votes
9 votes

Answer : 89
We can draw the recursion tree as follows, reusing the values wherever possible.

selected by
4 votes
4 votes

Answer is 89

Here is the recursion tree for the question.

In this the values in box represents what value will the function hold. We reuse the value of functions calculated.previously.

Answer:

Related questions

9 votes
9 votes
2 answers
2
5 votes
5 votes
3 answers
3
GO Classes asked Mar 26, 2022
513 views
What will be output printed by $\text{mystery}2(6)$?void mystery2(int n) { if (n 0) { printf("%d", n); mystery2(n-2); mystery2(n-3); printf("%d", n); } }
4 votes
4 votes
3 answers
4
GO Classes asked Mar 26, 2022
563 views
What will be the output printed by $\text{mystery}3(6)$?void mystery3(int n) { if (n == 0 || n == 1) return; mystery3(n-2); printf("%d", n); mystery3(n-1); }