使用递归将基数提高到其指数 - C++
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9348933/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Using Recursion to raise a base to its exponent - C++
提问by Ram Sidharth
I simply want to write some code that makes use of recursion of functions to raise a base to its power. I know that recursion is not the most right way to do things in C++, but I just want to explore the concept a bit. The program asks the user for a base and an exponent and then console outs the answer. Here's the program I've written:
我只是想编写一些代码，利用函数的递归来提升基础的能力。我知道递归不是在 C++ 中做事情的最正确方式，但我只是想稍微探索一下这个概念。该程序要求用户输入底数和指数，然后控制台输出答案。这是我写的程序：
#include <iostream>
#include <math.h>
using namespace std;
int raisingTo(int, int);
int main()
{
int base, exponent;
cout << "Enter base value: ";
cin >> base;
cout << "Enter exponent value: ";
cin >> exponent;
int answer = raisingTo(base, exponent);
cout << "The answer is: " << answer << endl;
char response;
cin >> response;
return 0;
}
int raisingTo(int base, int exponent)
{
if (exponent > 0)
return 1;
else if (exponent = 0)
{
int answer = (int) pow((double)base, raisingTo(base, (exponent - 1)));
return answer;
}
}
The funny thing is, when I run this program, it keeps returning the answer as '1'! Can someone please help me on this?
有趣的是，当我运行这个程序时，它一直将答案返回为“1”！有人可以帮我吗？
回答by Seagull
int raisingTo(int base, unsigned int exponent)
{
if (exponent == 0)
return 1;
else
return base * raisingTo(base, exponent - 1);
}
You have 3 main problems:
你有3个主要问题：
- You don't have to use pow function
- To compare number you should use
==as=is an assignment not compare. - You missed that if exponent is equal 0 you should return 1.
- 你不必使用 pow 函数
- 要比较数字，您应该
==按原样=使用赋值而不是比较。 - 你错过了如果指数等于 0 你应该返回 1。
回答by leftaroundabout
To make this an actual C++ answer – this is the kind of task where you might consider making it a template function, as this should work with any kind of number type.
为了使其成为实际的 C++ 答案——这是一种您可能会考虑将其设为模板函数的任务，因为这应该适用于任何类型的数字类型。
Recursion isin fact a good idea, but only if you make use of the benefits it can offer: it can avoid some of the multiplications, by factoring out low numbers from the exponent.
递归实际上是一个好主意，但前提是您要利用它可以提供的好处：它可以通过从指数中分解出较小的数字来避免一些乘法运算。
template <typename NumT>
NumT raiseTo(NumT base, unsigned exponent) {
if (exponent == 1) return base;
if (exponent == 0) return 1;
if (exponent%2 == 0) { NumT ressqrt = raiseTo(base,exponent/2)
; return ressqrt*ressqrt; }
if (exponent%3 == 0) { NumT rescubrt = raiseTo(base,exponent/3)
; return rescubrt*rescubrt*rescubrt; }
else return base * raiseTo(base, --exponent);
}
An example how many calculation this can save: suppose you want to raise a number to 19. That's 18 multiplications if you use the na?ve loop-like approach. With this solution, what happens is
举个例子，这可以节省多少计算：假设你想把一个数字提高到 19。如果你使用简单的类似循环的方法，那就是 18 次乘法。有了这个解决方案，会发生什么
- 19 isn't divisible by either 2 or 3, so calculate b? be-1, which is
- b18. Now 18 is divisible by 2, so we square be/2, which is
- b9. Where 9 is divisible by 3, so we cube be/3, which is
- b3. Where 3 is divisible by 3, so we cube be/3, which is
- b1, which is b.
- 19 不能被 2 或 3 整除，所以计算b？b e-1，即
- b 18。现在 18 可以被 2 整除，所以我们平方b e/2，即
- 乙9. 其中 9 可被 3 整除，所以我们对b e/3 进行立方，即
- 乙3. 其中 3 可被 3 整除，所以我们对b e/3 进行立方，即
- b 1，即 b。
That was only 1+1+2+2 = 6 multiplications, 1/3 of the necessary amount for the loop-like approach! However, note that this doesn't necessarily mean the code will execute much faster, as the checking of factors also takes some time. In particular, the %3on unsigneds is probably not faster than multiplication on ints, so for NumT==intit's not really clever at all. But it isclever for the more expensive floating point types, complex, not to speak of linear algebra matrix types for which multiplication may be extremely expensive.
那只是 1+1+2+2 = 6 次乘法，是循环方法所需数量的 1/3！但是，请注意，这并不一定意味着代码会执行得更快，因为检查因素也需要一些时间。特别是，%3on unsigneds 可能并不比ints上的乘法快，所以NumT==int它一点也不聪明。但它对于更昂贵的浮点类型来说是聪明的，complex更不用说乘法可能非常昂贵的线性代数矩阵类型。
回答by Ben Voigt
Here's a version with better complexity (O(lg exponent), instead of O(exponent)), which is conceptually similar to leftroundabout's version.
这是一个复杂度更高的版本（O(lg exponent), 而不是O(exponent)），它在概念上类似于 leftroundabout 的版本。
int raisingTo(int base const, unsigned int const exponent, int scalar = 1)
{
if (exponent == 0)
return scalar;
if (exponent & 1) scalar *= base;
return raisingTo(base * base, exponent >> 1, scalar);
}
It also uses tail recursion, which generally leads to better optimized machine code.
它还使用尾递归，这通常会导致更好的优化机器代码。
回答by Necrolis
Your problem lies here
你的问题就在这里
if (exponent > 0)
return 1;
else if (exponent = 0)
firstly, you've inverted the conditional (if the exponent is equal to zero, it should return), secondly, you are assigning and not comparing with the second if.
首先，您已经反转了条件（如果指数等于零，它应该返回），其次，您正在分配而不是与第二个比较if。
回答by ip_x
Here's a cleaner explanation with O(log n) complexity
这是 O(log n) 复杂度的更清晰的解释
public int fastPower(int base , int power){
if ( power==0 )
return 1
else if(power %2 == 0 )
return fastPower(base*base,power/2)
else
return base * fastPower(base,power-1)
}
This algo works on following simple rules of exponent
该算法适用于遵循简单的指数规则
base^0 = 1
base^power = base*base^(power-1)
base^(2*power) = (base^2)^power
Thus at each level, value of n is either half of what it was or it is little less than n . Thus the deppest the recursion will ever go is 1+log nlevels
因此，在每个级别， n 的值要么是原来的一半，要么略小于 n 。因此，递归的最深1+log n层次是级别
Information source
信息来源
