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

Question

我无法理解尾递归的概念，我想为类似斐波那契的函数制作一个尾递归版本， p1= n-3 ， p2= n-2 ， fx( p1 ) + fx( p2 ) 到目前为止是我想出的，但我不知道这是否是正确的方法，有人可以帮助我，任何帮助将不胜感激 p1= n-3 , p2= n-2 Long doCalc( long n ) { return n = = 0 ? 0 : ( n == 1 ? 1 : ( n == 2 ? 1 : (make( p1 ) + make( p2 )) ) ); }

代码输出正确的结果

但是当我实现尾递归时，我的方法是分裂和征服，但它不起作用并且输出是错误的

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

    return factor3(p1, n + a);
}

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

    return factor2(p2, n + a);
}

Answer 1

可悲的是，我没有足够的声誉来发表评论，但可以回答你的问题：

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

差不多是这样：既然你从 (a,b,c) = (0,1,1) 开始，并且你想通过添加倒数第二个和第三个来导出下一个数字，那么你的下一个数字（假设为 d）将是 a+乙

所以 (a,b,c,d) = (a,b,c,a+b)

这意味着当您查看下一次迭代时，您会“移动”剩下的所有内容，并且您的下一次调用将是 (b,c,a+b)，如 Andrey 所说