基本上算是有两个类型的求解方式：
1、递归方式，理解起来最直接，最方便，但是递归算法的空间复杂度大，在递归深度不断增大的情况下，内存会爆掉。
2、引入变量，把position-1 和 position-2 这两个变量分别使用x和y表示，每次计算累加值使用sum存储，这个时候进行n-2次循环，就能把位置为n的数组求出。
这种思想，有点类似某些语言（比如kotlin）中的尾递归优化。
具体代码如下
另外，也可以通过声明一个size = n的数组来辅助实现，但这个实现方式，空间的利用效率比不上上面的第二种方式，明明只需要三个变量就能搞定，偏偏要引入一个数组；时间效率上又 不如递归。所以，这里不再写了。
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println("method 1 : 第" + i + "个fab数 -> " + getFabNum1(i));
System.out.println("method 2 : 第" + i + "个fab数 -> " + getFabNum2(i));
}
}
/**
* 递归实现
*/
private static int getFabNum1(int position) {
if (position == 0 || position == 1) {
return position;
}
return getFabNum1(position - 1) + getFabNum1(position - 2);
}
/**
* non-递归实现
*
* @param position
* @return
*/
private static int getFabNum2(int position) {
if (position == 0 || position == 1) {
return position;
}
int x = 0;
int y = 1;
int sum = 0;
for (int i = 2; i <= position; i++) {
sum = x + y;
x = y;
y = sum;
}
return sum;
}
