递归求pow(x,n),该怎么处理

递归求pow(x,n)


long pow_rec(long x, long n){
if(1==n)
return x;
if(n&1)
return pow_rec(pow_rec(x,n/2),2) * x;
else
return pow_rec(pow_rec(x,n/2),2);
}

运行会出现段错误，求解释！
[解决办法]


long pow_rec(long x,long n)
{
  if(n == 0) return 1;
  long t = pow_rec(x*x, n/2);
  return n&1 ? t*x : t;
}

[解决办法]
这算法用递归效率太差了，基本是废柴

这是典型的 Fast Exponentiation 算法
[解决办法]

引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

<code>
long pow_rec(long x, long n){
if(1==n)
return x;
if(n&1)
return pow_rec(x,n/2)*pow_rec(x,n/2)* x;
else
return pow_rec(x,n/2)*pow_rec(x,n/2);
}
</code>
你原来程序本来就是个死循环

你这样又是把人家好端端的logn给硬拆成了线性。

他的递归逻辑就不对，这是改动最小的改法！

复杂度都改扯了改得少又有什么用

刚才看到你的，学习了

递归求pow(x,n),该怎么处理

热点推荐