斐波拉希数列

Fabonacci数列
这是一个金典的问题，下面是解fabonacci数列的两种解法

• 递归算法：该算法的执行次数杂度为2^n-1次，时间复杂度为O(2^n)，由于方法是递归调用，所以在调用之前，n,result,还有fabonacciRecurence方法的地址，都需要压栈，所以系统的开销比较大

private static int fabonacciRecurence(int n) {

		int result = 0;
		if (n == 1 || n == 0) {
			return 1;
		} else {
			return result = fabonacciRecurence(n - 1)
					+ fabonacciRecurence(n - 2);
		}

	}

• 递推算法：时间复杂度为O(n)

private static int fabonacciRecursion(int n) {
		int first = 1, second = 1;
		int result = 0;
		for (int i = 2; i <= n; i++) {
			result = first + second;
			first = second;
			second = result;
		}
		return result;
	}