4

在研究递归时，我试图让一个 C++ 示例函数在 javascript 中工作。

原始函数（来自斯坦福 CS106B）在这里：

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);

我下面的版本重复了太多次。我搞砸了什么基本的事情？我敢打赌这是 var half 的行...我从未尝试将函数分配给变量，所以这也是新领域...

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);
4

1 回答 1

9

JavaScript 没有整数除法，所以这一行：

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

在 JavaScript 中与 C++ 中的相应行不同。（例如，如果 ，expo === 5它将使用2.5第二个参数的值而不是预期的 2 进行递归。）如果使用>>运算符，则可以得到与整数除以 2 相同的效果：

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

PS我应该提到，在一般情况下，您可以使用Math.floor（或者Math.ceil如果分子和分母具有相反的符号）进行整数除法。如有必要，位级运算符还会将其参数转换为整数，因此您可以使用它((a/b)|0)来获取 quotient 的整数部分a / b。然后，您不必担心迹象。

PPS 使用起来可能会快一点

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

而不是

if (expo % 2 === 0)

测试是否expo是偶数。（C++ 代码也有类似的情况。）

于 2013-08-19T07:10:52.810 回答