斐波那契数列的递归实现

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、……

表达式：

F0=0，

F1=1，

Fn=Fn-1+Fn-2（n>=2，n∈N*）

C#的代码实现

        public static int fib(int n)

        {

            if (n < 2)

            {

                return n;

            }

            else

            {

                return fib(n - 1) + fib(n-2);

            }

        }

时间复杂度：递归的时间复杂度是非常大的。

T(n)=T(n-1) + T(n-2)

斐波那契数列时间复杂度：O(2的n次方),O(2^n)。

主函数的调用：

for (int i = 0; i < 10; i++)

 {

       Console.WriteLine(fib(i));

  }

输出结果为1到34的斐波那契数列。