What does fun2() do in general in the below recursive code ?

Question

 

int fun(int x, int y)
{
    if (y == 0)   return 0;
    return (x + fun(x, y-1));
}
 
int fun2(int a, int b)
{
    if (b == 0) return 1;
    return fun(a, fun2(a, b-1));
}

 

Answer 1

Recurrence relation for $fun (x, y)$ is

$fun(x, y) = x + fun(x, y-1) \\= 2x + fun(x, y-2) \\= \dots \\= yx + fun(x, 0) \\= yx$

That is $fun(x, y)$ returns the product of $x$ and $y$.

Now, recurrence relation for $fun2$ is 

$fun2(a, b) = a \times fun2(a, b-1) \\= a \times a \times fun2 (a, b-2) \\= \dots \\= a^b \times fun2(a, 0) \\= a^b \times 1 = a^b$. 

Just a small change of 

 if (b == 0) return 1;

to

 if (b == 0) return 0;

will have made $fun2$ return $0$ always. 

The given code returns $a^b$. 

Answer 2

its just doing this : X^y

Comments

Is it power?

---

yeah .