converting a c++ formula into javascript

Question

Whilst studying recursion, I attempted to get a C++ example function working in javascript.

The original function (from Stanford CS106B) is here:

int Raise (int base, int exp)
{
    if (exp == 0)
        return 1;

    else
    {
        int half = Raise(base, exp/2);  
        if (exp % 2 === 0)
            return half * half;
        else
            return base * half * half;
    }
}

Raise(3,5);

My version below recurses far too many times. What fundamental thing have I messed up? I bet it's the line with var half... I've never tried to assign a function to a variable, so that's also new territory...

function Raise (base, expo)
{
    if (expo === 0)
        return 1;

    else
    {
        var half = Raise(base, (expo/2));  

        if (expo % 2 === 0)
            return half * half;
        else
            return base * half * half;
    }
}

Raise(3,5);

Answer 1

JavaScript does not have integer division, so this line:

var half = Raise(base, (expo/2));

does not do the same thing in JavaScript as the corresponding line in C++. (If, for instance, expo === 5, it would recurse with a value of 2.5 for the second argument instead of the intended 2.) You can have the same effect as integer division by 2 if you use the >> operator:

var half = Raise(base, expo >> 1);

P.S. I should mention that in the general case, you can do integer division using Math.floor (or Math.ceil if the numerator and denominator have opposite signs). The bit-level operators also convert their arguments to integers if necessary, so you can use ((a/b)|0) to get the integer part of the quotient a / b. You then don't have to worry about signs.

P.P.S. It would probably be a tiny bit faster to use

if ((expo & 1) === 0)

rather than

if (expo % 2 === 0)

to test whether expo is even. (A similar thing goes for the C++ code.)