将递归程序转换为迭代程序

Question

一个朋友向我发起了挑战，要求我编写一个程序，输入三个整数 (int a, int n, int k) 并尽可能高效地计算出 a^n mod k

我想到了以下解决方案

public static int rec(int a,int n,int k) //calc a^n mod k
    {
        if(n == 1)
            return a % k; 
        int exp1 = rec(a, n/2, k), exp2 = exp1;
        if(n % 2 == 1)
            exp2 = rec(a, n/2 + 1, k);

        return (exp1 * exp2) % k;
    }

这是一个非常简单的递归解决方案，它依赖于这样一个事实：a^(b+c) mod d = (a^b mod d * a^c mod d) mod d，并且在理论上以对数时间运行。

但是在实践中，当我们测量我们的解决方案时，他的线性时间解决方案比我的解决方案更好。我怀疑这是因为我使用了递归而不是循环。这有意义吗？如果是这样 - 我该如何将此代码转换为迭代程序？

- Oria Gruber

---

Java递归很慢。在Java中没有尾递归优化。如果你想要性能，避免使用它。 - Boris the Spider

Answer 1

这有意义吗？

是的。正如Boris The Spider指出的那样，Java中没有尾部优化。

我怎么把这段代码变成迭代程序？

让我复制粘贴一个迭代解决方案来计算一个数字的幂，在这里。

int pow(int x, int n) {
int res = 1;
while(n > 0) {
    if(n % 2 == 1) {
        res = res * x;
    }
    x = x * x;
    n = n / 2;
}
return res;
}

免责声明：尽管上述代码在我看来看起来没问题，但我个人没有进行过测试。

- opensam