欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

递归求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));
        }
    }
}
相关标签: leetcode 递归法