专题：菲波那切数列与递归

不使用递归和数组求解斐波那契数列

题目：

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

用户输入项数完就告诉他该项的值（要求不使用递归和数组）

解：

核心代码如下：

public int run22(int n) {

        int result = 1;

        if (n > 2) {

            int first = 1;
            int second = 1;
            int third = 1;

            for (int i = 3; i <= n; i++) {
                for (int j = 1; j <= i; j++) {
                    if (j == (i - 2)) {
                        first = second;
                    }
                    if (j == (i - 1)) {
                        second = third;
                    }

                    if (j == i) {
                        third = first + second;
                    }
                }
                result = third;
            }
        }
        return result;
    }

/**

• 不用递归求菲波那切数列：

• 1,1,2,3,5,8.....

• f s t

• f s t

• f s t
  

*/

public int test7(int n) {
        int f = 1, s = 1, t = 1;
        if (n > 2) {
            for (int i = 3; i <= n; i++) {
                f = s;
                s = t;
                t = f + s;
            }
            return t;
        } else {
            return f;
        }
    }

使用数组的核心代码：

public int run21(int n) {
        int result = 1;
        int[] array = new int[100];
        for (int i = 0; i < n; i++) {
            array[i] = 1;
            if (i > 1) {
                array[i] = array[i - 1] + array[i - 2];
            }
            result = array[i];
        }
        return result;
    }

使用递归的核心代码：

public int run2(int n) {
        int result = 1;
        if (n > 2) {
            result = run2(n - 1) + run2(n - 2);
        }
        return result;
    }

通过求解斐波那契数列这个例子，以及使用的三种思路来看，递归的好处一目了然，代码量明显比其它两种思路少很多，而且思路更简单。

递归的核心思路其实就是一直循环直到最底层然后一层一层找回来，所以思考递归的第一步就是想最底层的情况，然后再考虑后面的递增情况。