java - 将递归方法更改为迭代方法

Question

我在将此递归方法 (recP) 转换为使用循环的方法 (itP) 时遇到问题。

public class Main {

    public static int recP(int n) {

        if (n <= 2)
            return 1;
        else
            return (recP(n - 3) * recP(n - 1)) + 1;

    }

    public static int itP(int n) {

        if (n <= 2)
            return 1;
        else
            //do something


    }

    public static void main(String[] args) {

        System.out.println(Main.recP(6)); //returns 9
        System.out.println(Main.itP(6)); //should return 9

    }

--

如果我手动执行此操作，使用递归公式计算recP(6)，我会列出工作步骤并在执行过程中填写缺失的详细信息:

P6 = (P3 X P5)+ 1 = (2 X 4) + 1 = 9
P3 = (P0 X P2) + 1 = 2
P5 = (P2 X P4) + 1 = (1 X P4) + 1 = 4
P4 = (P1 X P3) + 1 = (1 X 2) + 1 = 3  

--

我知道循环应该放在方法的 else 部分中，但我不知道该循环将如何工作。无法找出计算recP/itP 的公式。希望得到一些指导。

Answer 1

您需要“记住”最近计算的三个值，并使用它们来计算当前值:

public static int itP(int n) {
    if (n <= 2) {
        return 1;
    }

    int n3 = 1;
    int n2 = 1;
    int n1 = 1;

    for (int i = 3; i <= n; i++) {
        int m = n3 * n1 + 1;
        n1 = n2;
        n2 = n3;
        n3 = m;
    }
    return n3;
}