c++ - 指数递归与迭代的效率

Question

所以我正在尝试实现一种更有效的计算 2^n 的方法。

我知道您可以将它拆分为 O(logn) 并且使用递归很容易做到。你一直除以 2，然后在它为奇数(或类似的东西)时乘以较低的幂。问题是我手写了乘法，因为它适用于大数。所以它需要返回多个参数。

我能想到的一个解决方案是制作一对包含所有需要的信息。除此之外，尽管我试图弄清楚如何使用迭代来编写它。我能看到的唯一方法是使用某种数据结构，然后循环将 n 除以 2，并在 n 为奇数时存储该值。然后编写一个 for 循环并在每次迭代时检查该值是否包含在数据结构中。在我看来，这似乎是一项成本相对较高的操作。

它是否有可能最终比递归版本效率低？

我这样做是因为:

1. 我无法让 gnp 工作。
2. 我认为我正在通过编写大数类(class)并使用它来学习。

Answer 1

如果您要处理大数字，而不是重新发明轮子，您可能应该看看 GNU MP Bignum Library .

关于递归与迭代的问题，答案是你总是可以把它们写成等价的；一个递归函数，它只将自己称为 tail call与 while 循环一样高效(前提是您的编译器支持尾调用优化，但最常见的编译器支持)。例如，您描述的快速求幂函数的尾递归版本是(伪代码):

function fastExp(base, exponent, accumulator) {
  if(exponent == 0) {
    return accumulator;
  } else if(exponent % 2 == 0) {
    return fastExp(base * base, exponent/2, accumulator);
  } else {
    return fastExp(base, exponent-1, base * accumulator); 
  }
}

将此递归函数视为一个循环，其中循环条件为 exponent != 0，递归调用就像是 goto 到循环的开头. (顺便说一句，你需要在开始时用accumulator = 1调用它。)它等同于以下内容:

function fastExp(base, exponent) {
  var accumulator = 1;
  while(exponent != 0) {
    if(exponent % 2 == 0) {
      base *= base;
      exponent /= 2;
    } else {
      exponent -= 1;
      accumulator *= base;
    }
  }
  return accumulator;
}

所以你可以看到它们是等价的，因此将执行相同数量的操作。