c++ - 数的递归解提高到指数

嘿，我有一个问题要以多种方式解决x ^ n。其中之一涉及使用递归公式，它给我带来了麻烦。所以我对n> = 0的x ^ n使用递归的一种方式

int power2(int base, int power){
    if (power == 0)
        return 1;
    else if ( power == 1)
        return base;
    else
        return (base * power2(base, power - 1));
}

这对我来说很有意义，所以当我将X设置为2且N设置为4时，它正在减小作为计数器的幂，并且将2x2幂提高到3、4 * 2，将幂提高到2、8 * 2 =16。比方将幂提高到1，而我有一个基本情况，就是如果幂被提高到1，它只会返回底数。但是对于下一个，我必须使用三个公式来解决。

x0 = 1

如果n为偶数，则为

xn = [xn / 2] 2

如果n为奇数，则为

xn = x * [xn / 2] 2

所以我到目前为止

int power3(int base, int power){
    if(power == 0){
        return 1;
    }
    else if ( power == 1)
        return base;
    // if power is even
    if (power % 2 == 0){
        return base*(power3(base,(power/2)));
    }
    // if power is odd
    else{
        return 0;
    }
}

所以我只是想让偶数首先工作，当我设置x = 2和n = 4时，它返回8。这对我来说很有意义，因为当幂为4/2时，仅会循环两次以使其大于1。所以我真的在想办法让它再循环一次，同时又能忠实于我给出的公式。当我添加奇数基本情况时，程序将运行直到n ^ 5但n ^ 6返回32

最佳答案

您对公式的解释有些疑问。x^n if n is even = [x^n/2]2并不意味着:

base*(power3(base,(power/2))) //meaning x * [x^n/2]

宁愿你有

(power3(base,(power/2))) * 2

再次查看您的公式，即使它也不正确，应该是x^n if n is even = [x^n/2]^2
所以作为代码:

(power3(base,(power/2))) * (power3(base,(power/2)))

要么:

(power3(base * base,(power/2)))

您的整个功能可能应该是这样的:

int power3(int base, int power){
    if(power == 0){
        return 1;
    }
    else if ( power == 1) // you don't really need this case,
        return base;      // power == 0 is enough as base case
        // if power is even
    if (power % 2 == 0){
        return (power3(base * base,(power/2)));
    }
    // if power is odd
    else{
         return base * (power3(base * base,(power/2)));
    }
}

好的，因为您似乎仍然对奇怪的力量感到困惑。
您的power变量为int，因此您得到的整数除法意味着3/2 = 1而不是1.5(小数点后的所有内容都会被截断)。

现在让我们看一下函数中的奇数情况:

return base * (power3(base * base,(power/2)));

让我们假设base == 4和power == 5

return 4 * (power3(4 * 4,(5/2))); // 5/2 evaluates to 2

和说return 4 * (power3(4, 5 - 1))一样
然后返回(power3(4 * 4, 4 /2))，因为我们现在得到了偶数情况。

我们基本上只按照以下1个步骤执行这两个步骤。我认为我的解释听起来有些怪异，但希望对您有所帮助。