哪种方式更有效地执行功能(在时间复杂度方面),使用递归,使用while循环,还是两者兼而有之？

Question

我已经看到了"分而治之"算法的代码示例(或者,至少我认为是"分而治之") - 一组通用示例倾向于使用递归而另一组使用while循环.

这是递归示例:

...
if (exponent%2==0) 
{ 
return Power(base*base, exponent/2); 
} 
else if (exponent%2==1)
{ 
    return base*Power(base*base, exponent/2); 
} 
...

而且,这是while循环示例:

...
while (exponent>1)
{
    if (exponent%2 == 1)
        result *= base;
    exponent/=2;
    base *= base;
}
...

在这两种情况下,看起来它们实际上都是以相同数量的操作执行的.两种方法似乎采取的操作数量受到上限函数的约束T(exponent) = ?(log_2(exponent)).除非我的分析是错误的,否则我看不出一种方法比另一种更快.我认为递归方法在空间复杂度方面效率低于while循环方法,因为递归方法具有空间复杂度2*(log_2(exponent))(如果该分析是正确的).

while-loop方法的唯一优势是它具有较低的空间要求吗？

Answer 1

假设您使用的编译器是理智的,那么是......较低的空间要求是唯一的优势.

请注意,大多数编译器都允许有效处理尾递归,这种情况发生在函数仅将自身称为执行的最后一步时(请参阅文章中的示例).如上所述,你的递归算法不是尾递归的,因为返回之前的最后一步是乘法(base*Power),但是这可以通过添加一个累加器变量作为参数来改变,该参数在每次调用时相乘然后返回你达到的最后一个累加器.

示例代码:

...
int Power(int base, int exponent, int accumulator)
{
    if (exponent%2==0) 
    { 
        return Power(base*base, exponent/2, accumulator); 
    } 
    else if (exponent%2==1)
    { 
        return Power(base*base, exponent/2, accumulator * base); 
    } 
}
...

其中Power总是最初用累加器1调用(例如,你可以产生一个替代功能电源(a,b),只需要调用Power(a,b,1)).