递归到指数的递归解决方案

Question

嘿，我有一个问题，我必须以多种方式解决x^n。其中之一涉及使用递归公式，给我一个很难的时间。这样的方法之一我用递归对于x^N对于n> = 0

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它只是返回基地。但是对于我的下一个，我必须使用三个公式来解决它。

• X = 1
• X ^Ñ如果n是偶数= [X ^N/2]
• X ^Ñ如果n是奇数= X * [ X ^n/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

Answer 1

您对公式的解释有点问题。
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您的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.我认为我的解释听起来有点奇怪，但希望它有帮助。