lesterpierson123 lesterpierson123 - 2 months ago 20
Java Question

Triple Fibonacci using linear recursion in Java

I'm trying to code a linear recursive Triple Fibonacci (meaning Triple Fibonacci numbers are inspired by Fibonacci numbers but start with three predetermined values, each value afterwards being the sum of the preceding three values.)

One of the constraints is basically to make it tail recursive, but so far I haven't had any chance with this piece of code:

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


I'm having a hard time finding out why it's not working...

EDIT: The n in this case is a non-negative integer. So for example, 10 is supposed to return 105, or 5 is supposed to return 5.

Answer

EDIT Based on your edit, now I think the predetermined values should all be 1.

  1. Your initial call to the overload passed 0, 1, 2, but it should pass 1, 1, 1.
  2. Your recursive call is wrong. You should be shifting each parameter to the left and passing a new one that is a + b + c.
  3. You can avoid computing extra steps by passing n - 3 on the initial call to the overload and then returning c in the base case.

See the working code below:

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

Here are the first 10 numbers according to the above code:

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