366. 斐波纳契数列

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指：

前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

---

递归和迭代的区别

递归

基本概念:

程序调用自身的编程技巧称为递归,是函数自己调用自己.
一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量.递归的能力在于用有限的语句来定义对象的无限集合.
使用递归要注意的有两点:
1)递归就是在过程或函数里面调用自身;
2)在使用递归时,必须有一个明确的递归结束条件,称为递归出口.

递归分为两个阶段:

1)递推:把复杂的问题的求解推到比原问题简单一些的问题的求解;
2)回归:当获得最简单的情况后,逐步返回,依次得到复杂的解.

迭代:

利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B.
递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换.能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出.

---

1.数组法

public class Solution {
    /*
     * @param n: an integer
     * @return: an integer f(n)
     */
    public int fibonacci(int n) {
        if(1 == n || 2 == n) {
            return n-1;
        }
        int[] fib = new int[n];
        fib[0] = 0;
        fib[1] = 1;
        for(int i = 2;i<n;i++) {
            fib[i] = fib[i-1] + fib[i - 2];
        }
        return fib[n-1];
        // write your code here
    }
}

2.递归法

public class Solution {
    /*
     * @param n: an integer
     * @return: an integer f(n)
     */
    public static int fibonacci(int n) {
        if(n < 0) {
            return -1;
        }
        else if(1== n) {
            return 0;
        }
        else if(2 == n) {
            return 1;
        }
        else{
            return fibonacci(n-1)+fibonacci(n-2);
        }
        // write your code here
}

3.迭代法（变量法）

public class Solution {
    /*
     * @param n: an integer
     * @return: an integer f(n)
     */
    public static int fibonacci(int n) {
        int a = 0;
        int b = 1;
        int tmp = 0;
        if(1 == n) {
            tmp = a;
        }
        if(2 == n) {
            tmp = b;
        }
        if(n>2) {
            for(int i = 2;i<n;i++) {
                tmp = a+b;
                a = b;
                b = tmp;
            }
        }
        return tmp;

        // write your code here
    }