1.方法重载

所谓方法重载：在同一个类中出现若干个方法名字相同，但是方法的参数个数、类型、次序不同的情形，就称之为方法重载。

注意：方法的返回类型不作为判断是否是方法重载的依据。

例如，定义有以下若干方法

1). int add(int x,int y);
2). int add(int y,int x); //不构成方法重载，形参名字的次序不构成方法重载
3). int add(int x,int y,int z); //构成方法重载，参数的个数不同。
4). int add(int x,long y); //构成方法重载，参数的类型不同
5). int add(long x,int y); //构成方法重载，参数的次序不同
6). void add(int x,int y); //不构成方法重载，返回类型不作为判断依据。

综上所述：1,3,4,5 四个方法构成方法重载。

为什么返回的返回类型不作为方法重载的判断依据呢？假设有以下代码：

class Test{

    public static int add(int x,int y){
        return x+y;
    }
    public static void add(int x,int y){
        int z = x+y;
        return;
    }

   public static void main(String[] args){
         //这里出现了歧义性，就是我们俗称的模棱两可。编译器不知道调用哪个add方法？
         add(10,5);  //请问究竟是调用 int add(int,int)还是 void int(int,int)?

   }
}

2.递归

方法调用其本身的现象我们叫做递归

例如： 求5的阶乘可以使用递归实现。因为5！可以理解为4的阶乘乘以5，即： 5!=4!5 4!=3!4 ... 最终找到递归的出口，求1的阶乘。 1!=1

代码实现：

public static long jieCheng(long num){
  if(num == 1){
    return 1;
  }
  return num*jieCheng(--num);
}

public static void main(String[] args) {
  long result = 0;
  result = jieCheng(5);
  System.out.println(result);

}

使用递归要注意的事项: 1.要有出口,(是一个判断条件,一般要和我们if语句搭钩); 2.次数不宜过多,尽量不要出现递归表达式(因为方法调用要开栈,栈内存是有限的,很容易溢出);

例如： 求斐波那契数列的第n项。 什么是斐波那契数列？数列的前两项都是1，从第三项开始每一项是前两项之和，这样的数列称为斐波那契数列。 例如： 1,1,2,3,5,8,13...这样一个数列就是斐波那契数列。 求斐波那契数列第n项的值，就可以使用递归实现。

代码实现如下：

public static long fact(long n) {
   if(n==1 || n==2){
    return 1;
   }
   return fact(n - 1) + fact(n - 2); //递归表达式
}

public static void main(String[] args) {
   long n = 10;
   System.out.println(fact(n));
}

运行结果：
55

以上代码看似没有问题，可是当我们把n取值稍大些，比如；n=100, 运行时接近死机状态，几乎无法得到结果。之所以出现这样的情形，是因为返回值是一个递归表达式。对应以上程序进行改写优化如下。

/*
pre和next分别表示要求项的前两项值。
*/
public static long fact(long n,long pre,long next){
   if(n==2){
      return next;
   }
   return  fact(n-1,next,pre+next);
}

public static void main(String[] args) {
     long n = 100;
     System.out.println("第" + n + "项是：" + fact(n,1,1));
}

运行结果：
第100项是：3736710778780434371

上面的优化算法，虽然没有错，但是计算结果已经超出了long类型的存储范围，必须使用BigInteger来保存每次的计算结果，进一步改进方案如下：

public static BigInteger fact2(long n, BigInteger pre, BigInteger next){
   if(n==2){
       return next;
   }
   return  fact2(n-1,next,pre.add(next));
}

public static void main(String[] args) {
    long n = 100;
    BigInteger pre = new BigInteger("1");
    BigInteger next = new BigInteger("1");
    System.out.println("第" + n + "项是：" + fact2(n,pre,next));
}

运行结果：

第100项是：354224848179261915075

3.汉诺塔问题

问题描述： - 有三根相邻的柱子，标号为A,B,C。 - A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子C上。 - 每次只能移动一个圆盘，并且只能小圆片只能放在大圆盘上。

问题分析：

我们先假设只有一个盘子:方法很简答，就是从A->C 这里A表示的是起始的柱子，C表示结束的柱子 我们通常不只是有一个盘子，但是最后一个盘子一定是从A->C，所以我们把 N个盘子分成两部分：

第一部分是上面N-1个盘子，要先把这部分当作一个整体移动到 B柱（这里B柱表示的是过度柱），再把最下面的柱子 从A->C。

剩下的问题就是把 剩下N-1个柱子从 B 移动到C了。

到这里大家是不是感觉有点熟悉了；我们要把移动这 N-1个盘子 只需要把 上面的 （N-1）-1个盘子移动到==A柱（此时的中间柱）==，然后把最下面的盘子移动到 B->C 就可以了。

我们会发现：移动N-1个盘子与移动N个盘子思路一致，只是起始位置变成了B，中间位置变成了A。

那么我们是不是可以一直按着这个思路，移动N-i个盘子，直到最后 只剩一个盘子 即（n-1）== 1时，移动一次就结束了。

代码实现：

package recursion;

public class HanoiTowerDemo {

    /**
     * 传入n个盘子，编号从1..n，我就能按照汉诺塔的规则，a -> c ，b是辅助盘
     *
     * @param nDisks
     * @param a      起始柱子
     * @param b      辅助柱子
     * @param c      目标柱子
     */
    public static void hanoiTower(int nDisks, char a, char b, char c) {
        // 边界
        if (nDisks == 1) {
            // 直接一步到位，用不到b，a上的这一个盘子从a -> c
            move(nDisks, a, c);
            return;
        }
        // n >= 2，核心步骤1,先把顶上的 n -1个小盘子从a -> b,c作为辅助
        hanoiTower(nDisks - 1, a, c, b);
        // 核心步骤2.此时a上就剩下第n个盘子，一步到位将最大的这个盘子一次移动到c
        move(nDisks, a, c);
        // 核心步骤3.此时再把B上的这n-1个盘子从b -> c,a作为辅助
        hanoiTower(nDisks - 1, b, a, c);
    }

    /**
     * 将编号为n的盘子从sourceTower移动到destTower
     *
     * @param nDisks
     * @param sourceTower
     * @param destTower
     */
    public static void move(int nDisks, char sourceTower, char destTower) {
        System.out.println("编号为" + nDisks + "的盘子正在从" + sourceTower + "->" + destTower);
    }

    public static void main(String[] args) {
        hanoiTower(3, 'A', 'B', 'C');
    }
}

运行结果：

编号为1的盘子正在从A->C
编号为2的盘子正在从A->B
编号为1的盘子正在从C->B
编号为3的盘子正在从A->C
编号为1的盘子正在从B->A
编号为2的盘子正在从B->C
编号为1的盘子正在从A->C