我的递归解决方案不起作用，但 DP 解决方案有效，我不知道为什么

Question

我正在努力使用递归找到第 n 个斐波那契数的修改版本。 a1 = 0, a2 = 1, a3 = a1 + a2^2, a4 = a2 + a3^2...等等

fib(0, 1, n);
public static void fib(BigInteger t1, BigInteger t2, int n) {
    if (n == 3) {
        System.out.println(t1.add(t2.multiply(t2)));
    } else {
        fib(t2.multiply(t2), t1.add(t2.multiply(t2)), n - 1);
    }
}

答案适用于较小的数字。 fib(0, 1, 5) returns 5。但是，fib(6) returns 29 而不是 27

但是，我下面的 DP 解决方案输出了正确的值；

public static void fib(BigInteger t1, BigInteger t2, int n) {
    BigInteger[] bi = new BigInteger[n];
    bi[0] = t1;
    bi[1] = t2;
    for (int i = 2; i < n; i++) {
        bi[i] = bi[i-2].add(bi[i-1].multiply(bi[i-1]));
    }
    System.out.println(bi[n-1]);
}

fib(0, 1, 5) returns 5 和 fib(6) 输出 27。我似乎无法弄清楚为什么会这样。

Answer 1

递归解决方案与您提供的递归描述不符。您的调用传递了两个参数：

t2^2
t1 + t2^2

第一个不应该平方。

fib(t2, t1.add(t2.multiply(t2)), n - 1);

完成后，我得到了值 3 到 10 的以下结果：

1
2
5
27
734
538783
290287121823
84266613096281243382112

Answer 2

抱歉.. 我刚刚在我的递归调用中看到了一个错误。应该是

fib(t2, t1.add(t2.multiply(t2)), n - 1);

而不是

fib(t2.multiply(t2), t1.add(t2.multiply(t2)), n - 1);

我的递归解决方案不起作用，但 DP 解决方案有效，我不知道为什么

My recursion solution does not work but DP solution works and I don't know why

java

recursion

dynamic-programming

fibonacci