将递归函数转化为迭代函数

Question

任务：根据以下公式计算 a_n :

• a₀ = 1
• a₁ = 3
• a₂ = 5
• a_n = a_n-1 * a²_n-2 * a³_n-3

我无法将函数变为迭代形式。我已经知道如何以递归的方式进行操作了，请问该任务应该如何实现，以及一般情况下应该如何实现？

以下是我的递归代码：

public static BigInteger recurs(int bigInteger){
    BigInteger sum;

    if (bigInteger == 0) {
        sum = new BigInteger(String.valueOf("1"));
    } else if (bigInteger == 1) {
        sum = new BigInteger(String.valueOf("3"));
    } else if (bigInteger == 2) {
        sum = new BigInteger(String.valueOf("5"));
    } else {
        sum = recurs(bigInteger-1).multiply(recurs(bigInteger-2).pow(2).multiply(recurs(bigInteger-3).pow(3)));
    }

    return sum;

}

- user10581642

---

你能将实际问题作为文本包含在内，而不是链接吗？还有，你自己尝试解决它的方法。谢谢。 - achAmháin

我建议您在https://math.stackexchange.com/上提出问题。您可能会在那里得到更好的答案，因为这实际上只是一个伪装成编程问题的数学问题 ;) - Neuron

我会使用三个变量的循环，并将值称为“product”，而不是求和。顺便说一下，作为循环，这样会快得多。 - Peter Lawrey

顺便一提，String.valueOf(string)就等同于string。 - Peter Lawrey

这不是尾递归，因此迭代版本可能需要额外的数据结构，如堆栈。 - user3458

Answer 1

你需要记住最后三个值，并且每次都以最后一个值计算出一个新值。

public static BigInteger iter(int n) {
    BigInteger a = BigInteger.valueOf(1);
    BigInteger b = BigInteger.valueOf(3);
    BigInteger c = BigInteger.valueOf(5);
    switch (n) {
        case 0: return a;
        case 1: return b;
        case 2: return c;
        default:
            for (int i = 2; i < n; i++) {
                BigInteger next = c.multiply(b.pow(2)).multiply(a.pow(3));
                a = b;
                b = c;
                c = next;
            }
            return c;
    }
}

请注意，这是O(n)而不是O(n^3)

- Peter Lawrey

---

现在用闭式解决它，这样它就是O(1)。这是我们从一个400k+用户期望的 :) - President James K. Polk

@JamesKPolk 这对于类似的斐波那契数列是可以解决的，但我无法完成所需的数学计算 ;) - Peter Lawrey

是的，我认为它涉及到 t^3 - t^2 - 2t - 3 的根，Wolfram Alpha显示这些根有点复杂。 - President James K. Polk

Answer 2

你需要将最近三次的结果存储在三个变量中，并对它们应用公式。下面是一个使用 int 的简化示例。你可以通过使用 BigInteger 来增强这段代码，以便它也适用于更大的数字。

static int compute_iterative(int n) {
    if (n == 0) return 1;
    if (n == 1) return 3;
    if (n == 2) return 5;

    int a_n3 = 1;
    int a_n2 = 3;
    int a_n1 = 5;
    int a_n = a_n1;
    int i = 3;
    while (i <= n) {
        a_n = a_n1 * (int) Math.pow(a_n2, 2) * (int) Math.pow(a_n3, 3);
        a_n3 = a_n2;
        a_n2 = a_n1;
        a_n1 = a_n;
        i++;
    }
    return a_n;
}

使用 BigInterger 版本：

static BigInteger compute_iterative(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("Unsupported input value: " + n);
    }
    final BigInteger[] values = { BigInteger.valueOf(1), BigInteger.valueOf(3), BigInteger.valueOf(5) };
    if (n < values.length) {
        return values[n];
    }
    int i = 3;
    while (i <= n) {
        final BigInteger result = values[2].multiply(values[1].pow(2)).multiply(values[0].pow(3));
        values[0] = values[1];
        values[1] = values[2];
        values[2] = result;
        i++;
    }
    return values[2];
}

- Illyes Istvan

Answer 3

给你一个提示：

初始化一个大小为n的数组，用于存储答案。例如，第i个索引将存储a_i的答案。将a_0、a_1和a_2初始化为给定的值（在您的情况下为1、3和5）。现在从索引3开始迭代，并使用您的公式计算a_i。

- mettleap

---

顺便提一下，你可以使用一个数组，但并不是必须的。你只需要最后三个值。 - Peter Lawrey