我需要计算一种力量的力量。例如: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

08-06 04:43