递归的方式：
b^n = (b^(n/2))^2 若n是偶数
b^n = b*(b^(n-1)) 若n是奇数
迭代的方式
product：存储中间结果,初始化为1
b^n = (b^2)^(n/2) * product 若n是偶数
b^n = b^(n-1) * product*b 若n是奇数
递归方式比较简单，这里不再贴上实现的代码，下面是用迭代方式计算乘幂的Scala代码：
object expt{
def f(b:Int,n:Int,product:Int):Int={
if(n==1) b*product
else if(isOdd(n)) f(b,n-1,b*product)
else f(b*b,n/2,product)
}
def isOdd(n:Int)={
n%2 == 1
}
def expt(b:Int,n:Int)=f(b,n,1)
def main(args:Array[String])=
{
println(expt(2,10))
println(expt(2,11))
println(expt(5,9))
}
}
无论是递归算法还是迭代算法，时间复杂度都是O(lg(n))，递归算法的空间复杂度是O(lg(n))，迭代算法的空间复杂度是O(1)