在 Java 中使用线性递归的三重斐波那契数列

Question

我正在尝试编写线性递归三重斐波那契（意思是三重斐波那契数受斐波那契数的启发，但以三个预定值开始，之后的每个值都是前三个值的总和。）

其中一个约束基本上是使其尾递归，但到目前为止我还没有机会使用这段代码：

public class TailRecursiveOddonacci {

public long tailOddonacci(int n) {
    if (n <= 3) {
        return 1;
    }
    return tailOddonacciRecursion(0, 1, 2, n);
}

private long tailOddonacciRecursion(int a, int b, int c, int count) {
    if(count <= 0) { 
        return a;
    }
    return tailOddonacciRecursion(b, a+b, a+b+c, count-1);
}
}

我很难找出为什么它不起作用...

编辑：本例中的 n 是一个非负整数。因此，例如，10 应该是 return 105，或者 5 应该是 return 5.

Answer 1

编辑根据您的编辑，现在我认为预定值应该都是1。

您对重载的初始调用传递了 0、1、2，但它应该传递 1、1、1。
你的递归调用是错误的。您应该将每个参数向左移动并传递一个新参数 a + b + c.
您可以通过在初始调用重载时传递 n - 3 然后在基本情况下返回 c 来避免计算额外的步骤。

查看下面的工作代码：

public long tailOddonacci(int n) {
    if (n <= 3) {
        return 1;
    }
    return tailOddonacciRecursion(1, 1, 1, n - 3);
}

private long tailOddonacciRecursion(int a, int b, int c, int count) {
    if(count <= 0) {
        return c;
    }
    return tailOddonacciRecursion(b, c, a + b + c, count - 1);
}

public static void main(String[] args) {
    System.out.println(new Test().tailOddonacci(5));
}

根据上面的代码，这里是前 10 个数字：

1, 1, 1, 3, 5, 9, 17, 31, 57, 105

在 Java 中使用线性递归的三重斐波那契数列

Triple Fibonacci using linear recursion in Java

java

fibonacci