关于斐波那契线性递归函数的问题？
__int64 fib(int n,__int64 & prev){if(0 == n){prev=1;return 0;}
else{
__int64 prevPrev;
prev = fib(n-1,prevPrev);
return prevPrev + prev;
}
}
这段代码，是斐波那契的线性递归版本，递归计算前两项，用辅助变量记录前一项，返回数列的当前项，这段代码的运行过程是怎么样的能，能举个n=3的情况列个表给我看看吗？传引用过多有点迷 本帖最后由 TyCk 于 2018-7-17 16:29 编辑
感觉楼主代码好像有问题吧。
fib定义的参数应该是__int64 * prev 吧，第五行应该传址，为prev = fib(n-1,&prevPrev); 。
这样的话，
n = 3, 函数为fib(3,&prev) = prevPrev + prev，其中prev = fib(2,&prevPrev);
n = 2, 函数为fib(2,&prevPrev) = prevPrev2 + prevPrev,(用2作区分)，其中prevPrev = fib(1,&prevPrev2);
n= 1，函数为fib(1,&prevPrev2) = 0，执行后prevPrev2=1
自下而上依次计算代入即可。
楼主最好仔细看下指针的解引用、传址、传值、return等的区别。
按照楼主的描述，“斐波那契的线性递归版本，递归计算前两项，用辅助变量记录前一项，返回数列的当前项”，n=1时，return 0 是否合理？ 试了下楼主代码，也有点晕，看不太懂楼主的思路。
自己试了下，楼主可以考虑参考下。
//n为当前项索引值，返回当前项数值
int fib(int n)
{
if (0==n || 1==n)
{
return 1；
}
else
{
return (fib(n-1)+fib(n-2));
}
} TyCk 发表于 2018-7-17 16:46
试了下楼主代码，也有点晕，看不太懂楼主的思路。
自己试了下，楼主可以考虑参考下。
指数级的我会，我想知道那个复杂度为线性的具体运行过程{:10_266:} 御笔剑客 发表于 2018-7-17 20:18
指数级的我会，我想知道那个复杂度为线性的具体运行过程
好吧{:10_245:}这段代码，已经是能运行的吗？ TyCk 发表于 2018-7-17 21:17
好吧这段代码，已经是能运行的吗？
这是清华的一个教授写的线性递归版{:10_266:} 御笔剑客 发表于 2018-7-17 21:41
这是清华的一个教授写的线性递归版
哈哈，那应该是没错了，研究研究再说。{:10_284:} 流程画的很难看 不过我觉得应该是这样
页:
[1]