我的递归解决方案不起作用，但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）返回5.但是，fib（6）返回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）返回5和FIB（6）的输出27. 我似乎无法找出为什么是这种情况。

Answer 1

递归解决方案与您给出的重复描述不匹配。您的电话传递两个参数：

t2^2 
t1 + t2^2 

第一个不应该被平方。

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

上述工作完成后，我通过10得到值3的结果如下：

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);