Java递归实现斐波那契数列 Java递归实现斐波那契数列

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。——这是百度百科说的。

其实说白了，就是递归方法本身调用自己而进行的运算，下面举个例子说明一下这个例子就是很著名的——斐波那契数列。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……
可以看出来第三个数就是前面两个数相加从而得到的。

如果使用正常的循环进行解决的话就是这样：

public class FeiBo{
  public static void main(String[] args) {
    int num1=0;
    int num2=1;
    int numn=1;
    int n=10;
    for (int i = 3; i <=n; i++) {
      numn=num1+num2;
      num1=num2;
      num2=numn;
    }
    System.err.println(n+"个数的结果为："+numn);
  }
}

运行结果为：

10个数的结果为：34

这是使用正常的循环方法进行运算，如果使用递归的话就是一下这样：

public static int Recursion(int n){

    if(n==1){
      return 0;
    }

    if(n==2){
      return 1;
    }
    return Recursion(n-1)+Recursion(n-2);
  }

递归需要结束条件，到情况下递归就不需要继续调用，结束递归。上面案例结束条件就是当n=1或者2的时候，就返回0或者1，而不是继续调用递归方法本身了。

递归最主要的两个条件就是，自己调用自己，结束递归的条件。

因为递归是自己调用自己所以浪费资源大，运行时间比循环长很多，运行慢，效率底。