类斐波那契函数的尾部递归版本

Question

我很难理解尾部递归的概念，我想为类似斐波那契函数a（n-3）a（n-2）制作一个尾部递归版本，到目前为止，这是我提出的，但我不知道这是否是一个正确的方法，有人能帮我吗，任何帮助都将不胜感激

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

代码输出正确的结果

但是当我实现尾部递归时，我的方法是分而治之的，但它不起作用，输出是错误的

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

Answer 1

我认为原因如下：

1. 递归算法：

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

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

所以，（a，b，c）变成（b，c，a b），尾部递归是：

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

Answer 2

遗憾的是，我没有足够的声誉发表评论，只能回答你的问题：

首先，这个链接确实有助于理解如何实现解决方案。

基本上是这样的：因为你从（a，b，c）=（0,1,1）开始，然后你想通过把最后一个第二个和第三个相加得到下一个数字，你的下一个数字（假设为d）将是一个b

so（a，b，c，d）=（a，b，c，a b）

这意味着当你查看下一次迭代时，你“移动”了所有剩下的东西，你的下一个调用将是（b， c， a b），正如Andrey所说