java - 使递归函数迭代

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;

}

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)