题目2. 斐波那契数列-轻识

在面试美团的时候面试官给我出了这么一道类似的题目，给我一组数组，判断里面的数字是否为斐波那契数列中的元素，并标记这些元素在斐波那契数列中的下标。然后按照顺序输出出来。数组是随意的。

当时听到这个题目的时候我是一脸懵逼，因为我不知道斐波那契数列是怎么回事。经过面试官的解说之后，我开始思考这个东西怎么实现。然后用笔在会议室的墙上画了画，最后猛然醒悟这是一个递归。然后我一气呵成，找到递归结束条件，将代码完成了。之后又用HashMap进行了一些优化。面试下来，面试官说我的基础算法还是不错的，推理的过程也很符合逻辑，就是......，然后让我回去等消息去了。

今天我们先来完成leetcode中的一道小题509题。

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

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

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

给定 N，计算F(N).

示例 1：

输入：2

输出：1

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

代码如下，这个问题相通了就会非常简单，脑容量不够那就会和递归算法一样，导致栈溢出异常。递归结束条件就是数列前两个数，因此下标为1不是0。然后每个方法的结果依次从虚拟机栈中弹出，带给栈中的下一个方法进行计算。直到弹出完成，就得到了最后的结果。

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);
    }
}

输出结果如下：

1 1 2 3 5 8 13 21 34 。

虚拟机栈方法弹出顺序如下图所示：递归链条过长，必然会导致StackOverFlowException。因为虚拟机栈长度肯定是有规定的。