我需要计算一种力量的力量。例如:3^2^n。你可以把n当作输入,但是这个例子和9^n不一样。我用循环来写一个算法,但是现在我需要写递归的。我找不到有效的方法来写。
最佳答案
我继续用Ruby实现了这个,它非常接近伪代码,而且还有一个额外的好处就是可以测试由于ruby也有任意精度的整数运算,下面的代码使用非平凡的参数。
这个实现基于一个古老的技巧,即平方基并在指数为偶数时将其提高到指定幂的一半,因此递归堆栈的增长是对数的,而不是线性的幂这是从ilya的回答中得到的启发,但我发现y > 1 and n > 1
的情况不正确,这导致我在下面elif n > 1
行中实现的递归调用中使用递归调用:
def powpow(x, y, n)
if y == 0
return 1
elsif y == 1 || n == 0
return x
elsif n > 1
return powpow(x, powpow(y, n, 1), 1)
elsif y.even?
return powpow(x * x, y / 2, 1)
else
return x * powpow(x * x, y / 2, 1)
end
end
p powpow(3,2,5) # => 1853020188851841
我直接证实了这个结果:
irb(main):001:0> 2**5
=> 32
irb(main):002:0> 3**32
=> 1853020188851841