递归的几种算法

1.汉诺塔算法

有三根柱子，A柱子中从底部往上放着从大到小的柱子，现在要通过B、C两个柱子，将A柱子中的所以柱子移动到B柱子中， 并且在C柱子中所摆放的顺序也是从大到小

public class HanNoTa {
    private int i=1;
    public static void main(String[]args){
        HanNoTa hanNoTa=new HanNoTa();
        hanNoTa.hanNoTa(3,'A','B','C');

    }

    /**
     * 汉诺塔---有三根柱子，A柱子中从底部往上放着从大到小的柱子，现在要通过B、C两个柱子，将A柱子中的所以柱子移动到B柱子中，
     * 并且在C柱子中所摆放的顺序也是从大到小
     *
     * @param n
     * @param from
     * @param dependOn
     * @param to
     */
    public void hanNoTa(int n,char from,char dependOn,char to){
        if (n==1){
            move(n,from,to);
        }else{
            hanNoTa(n-1,from,to,dependOn);//第一步，先将n-1个盘子从A利用C挪到B
            move(n,from,to);//讲n这个盘子（底盘）从A挪到C
            hanNoTa(n-1,dependOn,from,to);//讲n-1个盘子从B利用A挪到C
        }

    }

    private void move(int n, char from, char to) {
        System.out.println(i+"-----------"+from+"---------"+to);
        i++;
    }
}

2.阶乘算法(10!)

public class CalNFact {
    public static void main(String[] args) {
        CalNFact calNFact = new CalNFact();
        int f = calNFact.f(5);
        System.out.print(f);

    }

    /**
     * 阶乘算法
     *
     * @param n
     * @return
     */
    public int f(int n) {
        if (n == 1) {
            return n;
        } else {
            return n * f(n - 1);
        }

    }
}

3.欧几里德算法

求两个数的最大公约数：指某几个整数共有因子中最大的一个。例如，12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数。

public class Gcd {

    public static void main(String[] args) {
        Gcd gcd = new Gcd();
        int x = gcd.gcd(99, 55);
        System.out.println(x);

    }

    /**
     * 欧几里德----求两个数的最大公约数：指某几个整数共有因子中最大的一个。
     * 例如，12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数。
     *
     * @param m
     * @param n
     * @return
     */
    public int gcd(int m, int n) {
        if (n == 0) {
            return m;
        } else {
            return gcd(n, m % n);
        }
    }
}

4.穷举

• 规定：第一个杯子只可以往第二个杯子中倒酒，第二个杯子只可以往第三个杯子中倒酒，第三个杯子只可以往第一个杯子中倒酒
• 第一个杯子往第二个杯子中倒酒的条件：第二个杯子的酒量为0；
• 第二个杯子往第三个杯子中倒酒的条件：第二个杯子的酒量不为0，同时第三个杯子的酒量没有超过它本身的容量；
• 第三个杯子往第一个杯子中倒酒的条件：第三个杯子的酒量已超过它本身的容量

public class ShareWine {
    public static void main(String[]args){
        ShareWine shareWine=new ShareWine();
        shareWine.backBottle(12,0,0);

    }

    public int b1=12;
    public int b2=8;
    public int b3=5;//b1.b2.b3是三个杯子
    public int m=4;//目标酒量

    /**
     * 穷举:
     * 规定：
     * 第一个杯子往第二个杯子中倒酒的条件：第二个杯子的酒量为0；
     * 第二个杯子往第三个杯子中倒酒的条件：第二个杯子的酒量不为0，同时第三个杯子的酒量没有超过它本身的容量；
     * 第三个杯子往第一个杯子中倒酒的条件：第三个杯子的酒量已超过它本身的容量
     * @param bb1
     * @param bb2
     * @param bb3
     * 三个参数是杯子的初始酒量
     */
    public void backBottle(int bb1,int bb2,int bb3){
        System.out.println(bb1+"---"+bb2+"---"+bb3);
        if (bb1==m||bb2==m||bb3==m){
            System.out.println("----");
            return;
        }

        if (bb2!=0&&bb3!=b3){//第二个杯子有酒，第三个杯子不满,这个时候把bb2里面的酒倒入bb3中
            if (bb2+bb3<=b3){
                //�倒不满第三个杯子
                backBottle(bb1,0,bb2+bb3);
            }else{
                //倒满第三个杯子
                backBottle(bb1,bb2-(b3-bb3),b3);
            }

        }else if (bb3==b3){//第三个杯子的酒是满的,这个时候需要往第一个杯子中倒酒
            if (bb1+bb3<=b1){
                //倒不满第一个杯子
                backBottle(bb1+bb3,bb2,0);

            }else {
                //倒满第一个杯子
                backBottle(b1,bb2,bb3-(b1-bb1));
            }

        }else if (bb2==0){//第二个杯子是空的时候，第一个杯子才可以往里面倒酒
            if (bb2+bb1<=b2){
                //倒不满第二个杯子
                backBottle(0,bb1,bb3);
            }else{
                //倒满第二个杯子
                backBottle(bb1-b2,b2,bb3);
            }

        }

    }

}