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

御笔剑客

1. __int64 fib(int n,__int64 & prev){
   
2.     if(0 == n){prev=1;return 0;}
   
3.     else{
   
4.     __int64 prevPrev;
   
5.     prev = fib(n-1,prevPrev);
   
6.     return prevPrev + prev;
   
7.     }
   
8. }

复制代码

这段代码，是斐波那契的线性递归版本，递归计算前两项，用辅助变量记录前一项，返回数列的当前项，这段代码的运行过程是怎么样的能，能举个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为当前项索引值，返回当前项数值

1. int fib(int n)
   
2. {
   
3.         if (0==n || 1==n)
   
4.         {
   
5.                 return 1；
   
6.         }
   
7.         else
   
8.         {
   
9.                 return (fib(n-1)+fib(n-2));
   
10.         }
    
11. }

复制代码

御笔剑客

TyCk 发表于 2018-7-17 16:46
试了下楼主代码，也有点晕，看不太懂楼主的思路。
自己试了下，楼主可以考虑参考下。

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

TyCk

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

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

御笔剑客

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

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

TyCk

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

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

一语终难尽思愁

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