返回意外负值

Question

这是一个简单的递归代码，用于计算厨师准备菜肴的方式，如果她有“n”套食物，“m”天提供服务，如果她不想在“k”天重复一次食物。

int ncomb(int n, int m, int k)
{
    if (k > n)  //1
        return 0;

    if (m == 1) //2
        return n;

    if (k == 0) //3
        return n * (ncomb(n, m-1, k) % 1000000007);

    else //4
        return n * (ncomb(n-1, m-1, k-1) % 1000000007);
}

由于条件1和3，代码中的返回值为n或0，且n永远不能低于，但是如果对于某些输入(例如，n-433、m-43、k-3)输出为负值，那么有人能知道为什么会发生这种情况吗？

Answer 1

int (签名int32)的最大值为0x7FFFFFFF，正好为2147483647。

在多重运算(return n * (ncomb(n, m-1, k) % 1000000007);)之后，您会溢出这个值。

尝试“长”(最多9223372036854775807)，而不是：

    long ncomb(long n, long m, long k)
    {
        if (k > n)  //1
            return 0;

        if (m == 1) //2
            return n;

        if (k == 0) //3
            return n * (ncomb(n, m-1, k) % 1000000007);

        else //4
            return n * (ncomb(n-1, m-1, k-1) % 1000000007);
    }