如何将此递归转换为循环？

Question

我正在考虑这个问题,比如我有一个幂函数的递归版本:

double pow(double base, int power){
    if(power == 1 || power == 0){
        return base;
    }
    else if(power % 2 == 0){ 
        double result = pow(base,power/2);
        return result * result;
    }
    else{
        double result = pow(base,(power-1)/2);
        return result * result * base;
    }

}

我的问题是如何将这个转换为while循环？

编辑:我知道这可以通过显式维护堆栈来完成,但在这种特殊情况下有没有机会不这样做？

Answer 1

看起来它是通过平方算法的取幂.

这是你如何迭代地做到这一点:

double pow(double base, int power)
{
    double result = 1;

    while (power != 0)
    {
        if (power % 2 == 1)
            result *= base;

        power /= 2;    
        base *= base;
    }

    return result;
}