递归求x的n次幂(C语言)
程序员文章站
2022-07-12 12:03:21
...
通过递归,减少累乘的次数。
1、n=0或x=1,直接返回1.
2、n>0,n为偶数,可将x^n拆分为 (x*x)^(n/2);
3、n>0,n为奇数,可将x^n拆分为x*(x*x)^((n-1)/2);
4、n<0,n为偶数,可将x^n拆分为1/((x*x)^(-n/2);
5、n<0,n为奇数,可将x^n拆分为1/(x*(x*x)^(-(n+1)/2);
附代码:
double myPow(double x, long n){
if(n==0||x==1){
return 1;
}
else if(n>0){
if(n%2==0){
return myPow(x*x,n/2);
}
else{
return x*myPow(x*x,(n-1)/2);
}
}
else{
if((-n)%2==0){
return 1/myPow(x*x,-n/2);
}
else{
return 1/(x*myPow(x*x,-(n+1)/2));
}
}
}