題目2. 斐波那契數(shù)列

????????在面試美團(tuán)的時(shí)候面試官給我出了這么一道類似的題目，給我一組數(shù)組，判斷里面的數(shù)字是否為斐波那契數(shù)列中的元素，并標(biāo)記這些元素在斐波那契數(shù)列中的下標(biāo)。然后按照順序輸出出來。數(shù)組是隨意的。

????????當(dāng)時(shí)聽到這個(gè)題目的時(shí)候我是一臉懵逼，因?yàn)槲也恢漓巢瞧鯏?shù)列是怎么回事。經(jīng)過面試官的解說之后，我開始思考這個(gè)東西怎么實(shí)現(xiàn)。然后用筆在會(huì)議室的墻上畫了畫，最后猛然醒悟這是一個(gè)遞歸。然后我一氣呵成，找到遞歸結(jié)束條件，將代碼完成了。之后又用HashMap進(jìn)行了一些優(yōu)化。面試下來，面試官說我的基礎(chǔ)算法還是不錯(cuò)的，推理的過程也很符合邏輯，就是......，然后讓我回去等消息去了。

今天我們先來完成leetcode中的一道小題509題。

斐波那契數(shù)，通常用 F(n) 表示，形成的序列稱為斐波那契數(shù)列。該數(shù)列由 0 和 1 開始，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。也就是：

F(0) = 0,? ?F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

給定 N，計(jì)算F(N).

示例 1：

輸入：2

輸出：1

解釋：F(2) = F(1) + F(0) = 1 + 0 = 1.

代碼如下，這個(gè)問題相通了就會(huì)非常簡(jiǎn)單，腦容量不夠那就會(huì)和遞歸算法一樣，導(dǎo)致棧溢出異常。遞歸結(jié)束條件就是數(shù)列前兩個(gè)數(shù)，因此下標(biāo)為1不是0。然后每個(gè)方法的結(jié)果依次從虛擬機(jī)棧中彈出，帶給棧中的下一個(gè)方法進(jìn)行計(jì)算。直到彈出完成，就得到了最后的結(jié)果。

public class FibonacciSequence {

    public static void main(String[] args) {

        int[] fibIndexArr = new int[]{1,2,3,4,5,6,7,8,9};
        int[] fibArr = new int[fibIndexArr.length];

        for (int index : fibIndexArr) {
            int element = fib(index);
            fibArr[index-1] = element;
        }
        for (int element : fibArr) {
            System.out.print(element+" ");
        }
    }

    /**
     *
     * @param N
     * @return
     */
    private static int fib(int N){
            if (N <= 1) {
                return N;
            }
            return fib(N-1) + fib(N-2);
    }
}

輸出結(jié)果如下：

1 1 2 3 5 8 13 21 34 。

虛擬機(jī)棧方法彈出順序如下圖所示：遞歸鏈條過長(zhǎng)，必然會(huì)導(dǎo)致StackOverFlowException。因?yàn)樘摂M機(jī)棧長(zhǎng)度肯定是有規(guī)定的。