本文共 1254 字，大约阅读时间需要 4 分钟。

斐波那契数列是犹如0、1、1、2、3、5、8、·····、fn这样的数，从前书本上一般介绍的方法都是递归的方法 
递归方法实现：

public static int FibonacciDigui(int n){        if (n == 0) {            return 0;        }        if (n == 1) {            return 1;        }        return FibonacciDigui(n - 1) + FibonacciDigui(n - 2);    } 
 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
  
 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9

虽然递归实现比较好理解，代码十分简洁，但是当n比较大的时候，效率会非常低，这点不难理解，因为递归实际上是实现的是一棵树，例如f(10)： 
 
如图可以看出递归中有许多的重复计算，所以当n比较大的时候，这个时间复杂度是呈指数增长的，效率会非常低。 
当然我们可以用其他的方式来实现，用非递归的方式，这里有两种方法，一种是使用变量的方式，一种是用数组。 
变量的方式：

public static int getFibonacciNum(int n){        int first = 0;        int second = 1;        int fn = 1;        for (int i = 2; i < n + 1; i++) {            fn = first + second;            first = second;            second = fn;        }        return fn;    } 
 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
  10 
  11 
  
 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
  10 
  11

数组的方式：

public static int getFibonacci(int n){        int[] array = new int[n + 1];        array[0] = 0;        array[1] = 1;        for (int i = 2; i < array.length; i++) {            array[i] = array[i - 1] + array[i - 2];        }        return array[n];    } 
 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
  
 
  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9

这两种非递归的方式效率在n比较大的时候将远高于递归实现方式。