关于斐波那契线性递归函数的问题？

御笔剑客

__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

感觉楼主代码好像有问题吧。
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 是否合理？

TyCk

试了下楼主代码，也有点晕，看不太懂楼主的思路。
自己试了下，楼主可以考虑参考下。

//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
试了下楼主代码，也有点晕，看不太懂楼主的思路。
自己试了下，楼主可以考虑参考下。

指数级的我会，我想知道那个复杂度为线性的具体运行过程

TyCk

御笔剑客 发表于 2018-7-17 20:18
指数级的我会，我想知道那个复杂度为线性的具体运行过程

好吧这段代码，已经是能运行的吗？

御笔剑客

TyCk 发表于 2018-7-17 21:17
好吧这段代码，已经是能运行的吗？

这是清华的一个教授写的线性递归版

TyCk

御笔剑客 发表于 2018-7-17 21:41
这是清华的一个教授写的线性递归版

哈哈，那应该是没错了，研究研究再说。

一语终难尽思愁

流程画的很难看 不过我觉得应该是这样