retagged by
525 views
2 votes
2 votes

How many times is foo activated (called), including the first "$\text{foo}(3,12)$"

$\text{max()}$ and $\text{min()}$ are functions that return maximum and minimum respectively.
 

int foo(int a, int b) {
    if (a==b) {
        return b;
    }
    int mn =min(a,b), mx =max(a,b);
        return foo(mn,mn) + foo( mx - mn , mn);
}
retagged by

3 Answers

2 votes
2 votes
The recurrence relation to count number of function call looks like,
$F(a,b)=1+F(min(a,b),min(a,b))+F(max(a,b)-min(a,b),min(a,b))$   if $a\neq b$
            =1              if $a= b$

$F(3,12)=F(3,3)+F(9,3)+1$

$F(9,3)=F(3,3)+F(6,3)+1$

$F(6,3)=F(3,3)+F(3,3)+1$

now ,$F(3,3)=1$ as a=b

putting the value in $F(6,3)$ we get ,

$F(6,3)=3$

$F(9,3)=5$

$F(3,12)=7$

so correct answer is 7.
edited by
Answer:

Related questions

5 votes
5 votes
3 answers
1
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); }