斐波那契数算法优化

在很多算法都用到了递归算法，谈到递归就难免要提到斐波那契数的算法。

最一般的算法如下(C#语法)：

private long Fibonacci(int n,out long m)        {            long t, r;            if (n == 1)            {                m=0;                return 1;            }            else if (n == 2)            {                m = 1;                return 1;            }            else if (n > 2)            {                t = Fibonacci(n - 1, out m);                r = t + m;                m = t;                return r;            }            else            {                m = 0;                return 0;            }        }

此处的最大优化在于保存计算项之前的每一项的值，每一项的计算只调用Fibonacci方法一次，实际调用Fibonacci方法的次数只有n-1次，如果n=33，那么调用Fibonacci方法只有32次。

看看方法的调用次数就可知算法的效率了。

1楼sueking1分钟前

an=1/√[（1+√5/2) n-(1-√5/2) n](n=1,2,3.....）（√5表示根号5）