什么是斐波那契数？

Wikipedia 的定义比较详细，大家可以参考一下。

斐波那契数是一系列连续顺序排列的整型数。主要特征就是当前数是前两位数之和。
例如：
1 1 2 3 5 8 13 21 34 55 89 144 。。。
或则以0为初始值：
0 1 1 2 3 5 8 13 21 34 55 89 144 。。。

思路：

1. 利用集合的特性，将数列依次存在集合中再输出
2. 循环动态计算，边计算边输出（最佳）
3. 利用递归调用

实现：

用ArrayList存储Fibonacci数列

public static void printFibonacciUsingCollection(int len) {
        ArrayList<Integer> fi = new ArrayList<>();
        fi.add(0);
        fi.add(1);
        for (int i = 2; i <= len - 1; i++) {
            fi.add(fi.get(i - 2) + fi.get(i - 1));
        }
        if (len < 1) {
            System.out.println("the length is invalid");
        } else if (len == 1) {
            System.out.println("Fibonacci series of length " + len + " are here:");
            System.out.println("[" + fi.get(0) + "]");
        } else if (len == 2) {
            System.out.println("Fibonacci series of length " + len + " are here:");
            System.out.println("[" + fi.get(0) + ", " + fi.get(1) + "]");
        } else {
            System.out.println("Fibonacci series of length " + len + " are here:");
            System.out.println(fi);
        }
    }

动态计算：
当前fn = fn-2 + fn-1
下一轮fn-2,fn-1的值将这样变换：
fn-2 = fn-1
fn-1 = fn

public static void printFibonacciWithoutCollection(int len) {
        int f0 = 0;
        int f1 = 1;
        int fi;
        if (len <= 0) {
            System.out.println("the length is invalid");
        } else {
            System.out.println("the fibonacci series of length " + len + " are here");
            if (len == 1) {
                System.out.println(f0);
            } else if (len == 2) {
                System.out.println(f0 + " " + f1);
            } else {
                System.out.print(f0 + " " + f1 + " ");
                for (int i = 3; i <= len; i++) {
                    fi = f0 + f1;
                    System.out.print(fi + " ");
                    f0 = f1;
                    f1 = fi;
                }
                System.out.println();
            }
        }
    }

递归调用：
f(n) = f(n-1) + f(n-2)
例如：计算f(4)
f0 = 0
f1 = 1
f(4) = f(2) + f(3) 转换成先计算f(2)和f(3)
f(2) = f(0) + f(1) = 1
f(3) = f(2) + f(1) = 2
再将计算出的结果返回
f(4) = f(2) + f(3) = 1 + 2 = 3

每次分解递归调用再回归

public static int findFibonacciUsingRecursion(int len) {
        int f0 = 0;
        int f1 = 1;
        int fn;

        if (len == 1) {
            return f0;
        } else if (len == 2) {
            return f1;
        } else {
            fn = findFibonacciUsingRecursion(len - 2) + findFibonacciUsingRecursion(len - 1);
            return fn;
        }
    }

完整代码

递归：

import java.util.*;

public class Test {

    public static void main(String[] args) {
        testPrintFibonacciUsingRecursion();
    }

   public static void testPrintFibonacciUsingRecursion() {
        System.out.println("Please enter a length greater than 0, -1 means to quit");
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        while (len != -1) {
            if (len <= 0) {
                System.out.println("the length is invalid");
            } else {
                System.out.println("the fibonacci series of length " + len + " are here:");
                for (int i = 1; i <= len; i++) {
                    System.out.print(findFibonacciUsingRecursion(i) + " ");
                }
                System.out.println();
            }
            System.out.println("Please enter a length greater than 0 again, -1 means to quit");
            len = in.nextInt();
        }
    }

    public static int findFibonacciUsingRecursion(int len) {
        int f0 = 0;
        int f1 = 1;
        int fn;

        if (len == 1) {
            return f0;
        } else if (len == 2) {
            return f1;
        } else {
            fn = findFibonacciUsingRecursion(len - 2) + findFibonacciUsingRecursion(len - 1);
            return fn;
        }
    }
}

非递归：

import java.util.*;

public class Test {

    public static void main(String[] args) {
        testPrintFibonacci();
    }
    public static void testPrintFibonacci() {
        System.out.println("Please enter a length greater than 0, -1 means to quit");
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        while (len != -1) {
            printFibonacciWithoutCollection(len);
//            printFibonacciWithoutCollection(len);
            len = in.nextInt();
        }
    }

    public static void printFibonacciUsingCollection(int len) {

        ArrayList<Integer> fi = new ArrayList<>();
        fi.add(0);
        fi.add(1);
        for (int i = 2; i <= len - 1; i++) {
            fi.add(fi.get(i - 2) + fi.get(i - 1));
        }

        if (len < 1) {
            System.out.println("the length is invalid");
        } else if (len == 1) {
            System.out.println("Fibonacci series of length " + len + " are here:");
            System.out.println("[" + fi.get(0) + "]");
        } else if (len == 2) {
            System.out.println("Fibonacci series of length " + len + " are here:");
            System.out.println("[" + fi.get(0) + ", " + fi.get(1) + "]");
        } else {
            System.out.println("Fibonacci series of length " + len + " are here:");
            System.out.println(fi);
        }
    }

    public static void printFibonacciWithoutCollection(int len) {
        int f0 = 0;
        int f1 = 1;
        int fi;
        if (len <= 0) {
            System.out.println("the length is invalid");
        } else {
            System.out.println("the fibonacci series of length " + len + " are here");
            if (len == 1) {
                System.out.println(f0);
            } else if (len == 2) {
                System.out.println(f0 + " " + f1);
            } else {
                System.out.print(f0 + " " + f1 + " ");
                for (int i = 3; i <= len; i++) {
                    fi = f0 + f1;
                    System.out.print(fi + " ");
                    f0 = f1;
                    f1 = fi;
                }
                System.out.println();
            }
        }
    }
}

输出结果：

Please enter a length greater than 0, -1 means to quit
0
the length is invalid
1
the fibonacci series of length 1 are here
0
2
the fibonacci series of length 2 are here
0 1
3
the fibonacci series of length 3 are here
0 1 1 
8
the fibonacci series of length 8 are here
0 1 1 2 3 5 8 13 
-1
Process finished with exit code 0