algorithm - 幂次幂的递归算法

Question

我需要计算一个幂的幂。例如:3^2^n。您可以将 n 视为输入，但此示例与 9^n 不同。我使用循环编写了一种算法，但现在我需要编写递归算法。我找不到一种有效的方式来编写它。

Answer 1

我继续在 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