斐波那契数列递归算法和非递归算法实现

斐波那契数列（1,1,2,3,5,8，...) 用函数表示为f(n)=f(n-1)+f(n-2) (n>2,f(1)=1,f(2)=1)

首先一般想到递归算法：

static int Fn(int n) { if (n <= 0) { throw new ArgumentOutOfRangeException(); } if (n == 1||n==2) { return 1; } return checked(Fn(n - 1) + Fn(n - 2)); // when n>46 memory will overflow }递归算法时间复杂度是O(n2), 空间复杂度也很高的。当然不是最优的。 自然我们想到了非递归算法了。 一般的实现如下： static int Fn1(int n) { if (n <= 0) { throw new ArgumentOutOfRangeException(); } int a = 1; int b = 1; int c = 1; for (int i = 3; i <= n; i++) { c = checked(a + b); // when n>46 memory will overflow a = b; b = c; } return c; }