java - 在 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 应该返回 105，或者 5 应该返回 5。

Answer 1

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

1. 您对重载的初始调用传递了 0, 1, 2，但它应该传递 1, 1, 1。
2. 你的递归调用是错误的。您应该将每个参数向左移动并传递一个新参数，即 a + b + c。
3. 您可以通过在对重载的初始调用中传递 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