I am having trouble understanding the concept of tail recursion, I want to make a tail recursive version for Fibonacci-like function a( n - 3 ) a( n - 2 ) and so far this is what I came up with but I don't know if it's a correct approach, can someone help me out, any help would be appreciated

Long doCalc( long n )
{
    return n == 0 ? 0 : ( n == 1 ? 1 : ( n == 2 ? 1 : (doCalc( n - 3 )   doCalc( n - 2 )) ) );
}

the code outputs the correct result

but when i implement the tail recursive , my approach was split and conquer, but it's not working and the output are wrong

Long factor3(Long n, Long a)
{
    if( n == 0){
        return 0l;
    } else if( n == 1 || n == 2) {
        return a;
    }

    return factor3(n - 3, n   a);
}

Long factor2(Long n, Long a)
{
    if( n == 0){
        return 0l;
    } else if( n == 1 || n == 2) {
        return a;
    }

    return factor2(n - 2, n   a);
}

CodePudding user response：

I believe the reasoning is following:

1. recursive algorithm:

    public static Long doCalcRecursive(long n) {
        return n == 0 ? 0 : (n == 1 ? 1 : (n == 2 ? 1 : (doCalcRecursive(n - 3)   doCalcRecursive(n - 2))));
    }

2. after turning it into iterative we get:

    public static Long doCalcIterative(long n) {
        long a = 0, b = 1, c = 1, d;
        if (n == 0) {
            return a;
        }
        for (int i = 2; i <= n; i  ) {
            d = a   b;
            a = b;
            b = c;
            c = d;
        }
        return b;
    }

so, (a,b,c) turns into (b,c,a b) and tail recursion is:

    public static long doCalcTail(long n, long a, long b, long c) {
        return n == 0 ? a : n == 1 ? b : n == 2 ? c : doCalcTail(n - 1, b, c, a   b);
    }

CodePudding user response：

Sadly, I do not have enough reputation to comment, but to answer your question:

First of all, this link really helps to understand how to achieve the solution.

It's pretty much: Since you start with (a,b,c) = (0,1,1) and you want to derive the next number by adding the second and third last, your next number (hypothetically d) would be a b

so (a,b,c,d) = (a,b,c,a b)

Which means when you look at the next iteration, you "shift" everything left and your next call will be (b,c,a b) as stated by Andrey