在java中,如果你第二次调用相同的函数,程序会"记住"结果吗？

Question

当我在思考快速计算数字能力的算法时,就会出现这个问题,比如计算x^n.

在Java中,递归部分类似于:

return power(x,n/2) * power(x,n/2);

所以在程序返回值之后power(x,n/2),它会再次通过整个递归过程来计算第二个值power(x,n/2)吗？

如果是这样,我们应该先将值存储在某个变量中,然后返回该值的平方吗？

Answer 1

你所记得的是memoization:一个纯函数(即一个返回值仅取决于参数值的函数)可以记住它以前遇到的参数的结果.

Memoization由一些高级特殊用途语言(如Maple)执行.但是,默认情况下,通用语言不具有此(相当复杂)的行为.

但是,在您的情况下,这不是必要的.您的算法不是使用递归,而是更好地实现为迭代.通过重复平方的二进制求幂是标准算法.

这是一些类似C的伪代码(我的Java不是100%):

// compute pow(base, exponent)

int result = 1;
int term = base;

while (exponent != 0)
{
  if (exponent % 2 != 0) { result *= term; }
  term = term * term;
  exponent /= 2;
}

return result;

对于一些示例,7是二进制的111,因此b ⁷  =  b ¹  ×  b ²  ×  b ⁴,并且我们仅需要跟踪运行项的一个副本.另一个:5 = 101b,所以b ⁵  =  b ¹  ×1×  b ⁴.

_{在C++中,为任何R f(T1, T2, ..., TN)将内存存储在哈希映射中的函数构建通用的memoizing包装器非常容易std::unordered_map<std::tuple<T1, ..., TN>, R>; 在调用时,包装器检查参数元组是否已经存在,如果是,则返回映射中的值,如果不是,则执行计算并将结果插入映射中.我确信类似的东西可以用Java来装配.}