What will this recursive function yield?

Question

I have a recursive function g3, which I cannot understand what is the logic behind it, and what it actually does in general case.
double g3(double n) {
    if (n <= 1)
    {
        return 2;
    }
    double temp = g3(n / 2);
    return temp * temp;
}

For 1 I got 2
For 2 I got 4
For 3 I got 16
For 4 I got 16

Can you help me understand what it does?

amit · Answer

You could start by analyzing the cases, going from stop clause up, and looking not only on the "number" but what it represents:
g3(1) = 2 = 2^1
g3(2) = g3(1)^2 = 2^2
g3(4) = g3(2)^2 = (2^2)^2 = 2^4
g3(8) = g3(4)^2 = (2^4)^2 = 2^8
g3(16) = g3(8)^2 = (2^8)^2 = 2^16

So, this is pretty clear (I hope) what happens when n = 2^k for some integer k.

Can you prove it?
Can you repeat the process to answer what happens when n != 2^k for some integer k ?

What will this recursive function yield?

One Answer

Add your own answers!

Ask a Question