斐波那契数列 （C#）

斐波那契数列（fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（leonardoda fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34...

                                                             ---百度百科

1 >>>数组        很好理解。

 求第a位的数是多少?

第a位在循环中的下标是a-1。所以返回list[a-1];

public static int fbnq(int a)
        {
            int[] list = new int[a];
            list[0] = 1;
            list[1] = 1;
            for (var i = 2; i < a; i++)
            {
                list[i] = list[i - 1] + list[i - 2];
            }
            return list[a - 1];
        }

 

2 >>>递归         很简洁，难理解，耗性能。

  求第a位的数是多少?

递归有终点。本例终点就是a<=2的时候返回值是1。

讲解：例如传入的a是30,求第30位是多少？

30进入函数执行:后边的语句。执行时 她发现需要fbn1(29)+fbn1(28)，又发现29需要27+28，28需要27+26...... 直到到fbn1(0)+fbn1(1)【a<=2时】。函数有了值1

然后一路加回去，便求出fbnq(30).

public static int fbnq1(int a)
        {
            return a <= 2 ? 1 : fbnq1(a - 1) + fbnq1(a - 2);
        }

 学习阶段，有错误还望指出，谢谢！