题目：
写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：
知识点：
递归：是在一个函数的内部调用这个函数自身。循环：则是通过设置计算的初始值及终止条件，在一个范围内重复运算。
通常基于递归实现的代码比基于循环实现的代码要简介很多，更加容易实现。如果面试官没有特殊要求，应优先采用递归的实现方法。
递归虽然简介明了，但是缺点很明显：递归是函数自身调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据是需要时间。递归有可能很多计算都是重复的，从而对性能带来很大的负面影响。递归的本质是把一个问题分解成两个或多个小问题。如果多个小问题存在重叠的部分，，那么就存在重复的计算。斐波那契数列就是一个例子。
递归还可能引起调用栈溢出。因为递归每调用一次就在栈内存中分配空间，每个进程的栈容量都是有限的，故当递归调用的层级太多时，就会超出栈的容量，从而导致栈溢出。
第一思想：
求斐波那契数列第n项，是在我们课本上以讲解递归的例子出现的。故第一思想就是用递归实现。
递归代码：
//递归实现
public long fibonacci(int n){if(n <= 0){return 0;}if(n == 1){return 1;}return fibonacci(n - 1) + fibonacci(n - 2);
}优化思想：
上面用递归实现的斐波那契数列时间复杂度为n的指数，在我们传入的n为100时，计算机计算结果都需要等很长一段时间，再大时计算机直接崩溃。因此我们可以考虑用循环去代替递归。递归是由第n项去求第n-1项以此类推在遇到n=1或者n=0时再反过来计算即由大去推导小的，再通过小的去求大的，使栈的深度太大。我们可以直接用小的去求大的，这样可以避免栈的问题。并且时间复杂度为O（n）。
//利用循环实现
public long fibonacciByFor(int n){int result[] = {0, 1};if(n < 2){return result[n];}long fibNMiousOne = 0;long fibNMiousTwo = 1;long fibN = 0;for (int i = 2; i <= n; ++i) {fibN = fibNMiousOne + fibNMiousTwo;fibNMiousOne = fibNMiousTwo;fibNMiousTwo = fibN;}return fibN;
}最优解思想：
是根据推导斐波那契数列的一个矩阵数学公式
有兴趣可以去实现一下。我就只提供一种思路。它基于递归实现斐波那契的时间复杂度为O（logn）。
小结：
学会递归思想，需要深刻理解递归。
