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

Question

我很难理解尾递归的概念，我想做一个类似斐波那契函数的尾部递归版本，p1= n-3 p2= n-2 fx(p1) + fx(p2)到目前为止，这是我想到的，但我不知道这是否是一个正确的方法，有人可以帮助我，任何帮助都会很感激P1 = n-3 p2= n-2长doCalc(长n)｛返回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+b

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

这意味着当你看下一个迭代时，你"shift";所有剩下的东西，你的下一个呼叫将是(b,c,a+b)，正如安德烈所说的

Answer 2

我认为理由如下:

1. 递归算法:

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

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