C语言 递归幂函数：方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22389184/
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
Recursive power function: approach
提问by MoSFeT
I'm programming for a while now(beginner), and recursive functions are a somewhat abstract concept for me. I would not say I'm stuck, program works fine, I'm just wondering if the function itself could be written without the pow function in the code (but still doing exactly what the problem suggests)
我现在编程了一段时间（初学者），递归函数对我来说是一个有点抽象的概念。我不会说我卡住了，程序运行良好，我只是想知道是否可以在代码中没有 pow 函数的情况下编写函数本身（但仍然完全按照问题的建议进行操作）
Problem: http://prntscr.com/30hxg9
My solution:
我的解决方案：
#include<stdio.h>
#include<math.h>
int power(int, int);
int main(void)
{
int x, n;
printf("Enter a number and power you wish to raise it to: ");
scanf_s("%d %d", &x, &n);
printf("Result: %d\n", power(n, x));
return 0;
}
int power(int x, int n)
{
if (n == 0) return 1;
if (n % 2 == 0) return pow(power(x, n / 2), 2);
else return x * power(x, n - 1);
}
I've tried doing this: power(power(x, n - 1), 2); but execution failed, and I'm still backtracking why.
我试过这样做： power(power(x, n - 1), 2); 但是执行失败了，我仍在回溯原因。
回答by Peter
When rewriting your function, don't lose sight of the main benefit of recursion in this case, which is to reduce the number of multiplication operations required. For example, if n = 8, then it is much more efficient to compute x * x as val1, then val1 * val1 as val2, and the final answer as val2 * val2 (3 multiplications) than to compute x * x * x * x * x * x * x * x (7 multiplications).
在重写函数时，不要忽视递归在这种情况下的主要好处，即减少所需的乘法运算次数。例如，如果 n = 8，那么将 x * x 计算为 val1，然后将 val1 * val1 计算为 val2，将最终答案计算为 val2 * val2（3 次乘法）比计算 x * x * x * 要高效得多x * x * x * x * x（7 次乘法）。
This difference is trivial for small integers but matters if you put this operation inside a big loop, or if you replace the integers with very large number representations or maybe ginormous matrices.
这种差异对于小整数来说是微不足道的，但是如果您将此操作放入大循环中，或者如果您用非常大的数字表示或可能是巨大的矩阵替换整数，则很重要。
Here's one way to get rid of the pow() function without getting rid of the recursion efficiency:
这是在不消除递归效率的情况下摆脱 pow() 函数的一种方法：
#include<stdio.h>
#include<math.h>
int power(int, int);
int main(void)
{
int x, n;
printf("Enter a number and power you wish to raise it to: ");
scanf_s("%d %d", &x, &n);
printf("Result: %d\n", power(x, n));
return 0;
}
int power(int x, int n)
{
int m;
if (n == 0) return 1;
if (n % 2 == 0) {
m = power(x, n / 2);
return m * m;
} else return x * power(x, n - 1);
}
回答by Harry Broeders
The code:
编码：
int power(int x, int n)
{
if (n == 0) return 1;
if (n % 2 == 0) return power(power(x, n / 2), 2);
else return x * power(x, n - 1);
}
does not work because when n is even power is called with n = 2 which is even and then power is called with n = 2 which is even and then power is called with n = 2 ... until ... stack overflow!
不起作用，因为当 n 是偶数时，用 n = 2 调用幂，这是偶数，然后用 n = 2 调用幂，这是偶数，然后用 n = 2 调用幂......直到......堆栈溢出！
Simple solution:
简单的解决方案：
int power(int x, int n)
{
if (n == 0) return 1;
if (n % 2 == 0) {
if (n == 2) return x * x;
return power(power(x, n / 2), 2);
}
else return x * power(x, n - 1);
}
回答by Héctor Asencio L
For the power function (let's say, x to the nth power) you have two cases:
对于幂函数（假设是 x 的 n 次幂），您有两种情况：
exponent=0
exponent=n
For the first case, you only need to return 1. In the other case, you need to return x to the power of n minus one. There, you only used the function recursively.
对于第一种情况，您只需要返回 1。在另一种情况下，您需要返回 x 的 n 减 1 次方。在那里，您只是递归地使用了该函数。
int power(int x, n)
{
if(n == 0) return 1;
else return x * power(x, n-1);
}
回答by suresh
double result = 1;
int count = 1;
public double power(double baseval, double exponent) {
if (count <= Math.Abs(exponent)){
count++;
result *= exponent<0 ?1/baseval:baseval;
power(baseval, exponent);
}
return result;
}
This works with positive, negative, and 0 value
这适用于正值、负值和 0 值
回答by Vbp
Here is a solution in rubywhich works for negative exponents as well
这是ruby中的一个解决方案，它也适用于负指数
# for calculating power we just need to do base * base^(exponent-1) for ex:
# 3^4 = 3 * 3^3
# 3^3 = 3 * 3^2
# 3^2 = 3 * 3^1
# 3^1 = 3 * 3^0
# 3^0 = 1
# ---------------------------------------------------------------------------
# OPTIMIZATION WHEN EXPONENT IS EVEN
# 3^4 = 3^2 * 3^2
# 3^2 = 3^1 * 3^1
# 3^1 = 3^0
# 3^0 = 1
# ---------------------------------------------------------------------------
def power(base, exponent)
if(exponent.zero?)
return 1
end
if(exponent % 2 == 0)
result = power(base, exponent/2)
result = result * result
else
result = base * power(base, exponent.abs-1)
end
# for handling negative exponent
if exponent < 0
1.0/result
else
result
end
end
# test cases
puts power(3, 4)
puts power(2, 3)
puts power(0, 0)
puts power(-2, 3)
puts power(2, -3)
puts power(2, -1)
puts power(2, 0)
puts power(0, 2)
回答by Nodar Maruashvili
My approach with C++, works only with non-negative numbers.
我的 C++ 方法仅适用于非负数。
#include <iostream>
using namespace std;
long long power(long long x, long long y) {
if (y == 0) {
return 1;
}
else {
y--;
return x*power(x,y);
}
}
main() {
long long n, x;
cin >> n >> x;
cout << power(n,x);
}
回答by devil_io
int pow(int a, int n) {
if(n == 0) return 1;
if(n == 1) return a;
int x = pow(a, n/2);
if(n%2 == 0) {
return x*x;
}
else {
return a*x*x;
}
}
回答by Sarthak Das
You want to avoid using pow(), right? So you used power()instead, leading to a recursive call within the argument list. This led to a segmentation fault.
你想避免使用pow()，对吗？所以你power()改用了，导致在参数列表中进行递归调用。这导致了分段错误。
First of all, let us understand the cause of the problem. I did a pen and paper run of the algorithm and the result is pretty interesting. It turns out that for any values of x and n, after a certain number of recursions one always ends up getting power(1, 2). This also means that power(1, 2)also leads to power (1, 2)after a certain number of recursions. Thus, this power()within a power()leads to an infinite recursionand thus the stack overflow.
首先，让我们了解问题的原因。我对算法进行了笔和纸运行，结果非常有趣。事实证明，对于 x 和 n 的任何值，经过一定次数的递归后，总会得到power(1, 2)。这也意味着在一定数量的递归之后power(1, 2)也会导致power (1, 2)。因此，该power()一个内power()引线到无限递归，因而堆栈溢出。
Now, to your question. Yes, this can be done without using pow() because pow(a, 2) can simply be written as a*a. So, here is a slight modification to your code:
现在，回答你的问题。是的，这可以在不使用 pow() 的情况下完成，因为 pow(a, 2) 可以简单地写为 a*a。因此，这里对您的代码稍作修改：
int power(int x, int n)
{
if (n == 0) return 1;
if (n % 2 == 0) return power(x, n / 2) * power(x, n / 2);
else return x * power(x, n - 1);
}
But then, why do it this way? A more efficient way would be as follows.
但是，为什么要这样做呢？更有效的方法如下。
int power(int x, int n)
{
if (n == 0) return 1;
if (n % 2 == 0) return power(x * x, n / 2);
else return x * power(x * x, n / 2);
}
This reduces the number of recursions needed, making the code more time and space efficient. Hope this helps!
这减少了所需的递归次数，使代码更节省时间和空间。希望这可以帮助！
回答by Ryan
Simple but does n number of multiplications. Above examples are more efficient because they group two operations in one iteration
简单但做 n 次乘法。上面的例子效率更高，因为它们在一次迭代中将两个操作组合在一起
int power(int x, int n)
{
if (n == 0) return 1;
return x * power(x, n-1);
}
