递归

简介

递归 问题是数学中一种解决问题的思想，和递推刚好是相对的。我们说 递推 就是讲一个问题从正面入手一点一点的抽丝剥茧，而 递归 则是从敌后直捣黄龙。

例子

这里我创建了一个 Recursion 类，类中定义了 getRecursion 方法，使用 getRecursion 进行递归调用，实现从10递减到0的操作。

public class Recursion{

    public static void getRecursion(int i) {
        System.out.println(i);
        if (i > 0){
            i--;
            getRecursion(i);
        }
    }

    public static void main(String[] args) {
        int i = 10;
        getRecursion(i);
    }
}

汉诺塔问题

这里我不再讲解汉诺塔问题的描述，如果不清楚的可以自行去百度了解。

汉诺塔问题我们可以从三阶汉诺塔分析

常见的三阶汉诺塔运用递归思想我们可以理解为三个子问题：

1. 从 A 我们将上面两层转移到 B
   

   从A到B问题

2. 从 A 我们将最下面一个元素转移到 C
   

   从A将最下面的转移到C

3. 从 B 我们将之间从 A 转移到 B 的两层转移到 C
   

   从B转移到C

Java代码实现

public class Recursion{

    /*
    * n 表示汉诺塔的阶数
    * a，b，c 代表三个杆子，其中 a 表示要转移的的杆子，b 代表中间转换的杆子，c 代表目标杆子
    * 总共分为三步
    **/
    public static void hanoi(int n,String a,String b,String c){
        if (n > 0){
            //第一步，将 A 中除最后一个都转移到 B
            hanoi(n-1,a,c,b);
            //将 A 的最下面一个转移到 C
            System.out.println(" move " a + " to " + c);
            //将 B 的所有元素转移到 C
            hanoi(n-1,b,a,c);
        }
    }

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

当然以后的更多层的汉诺塔我们同样也可以用同样的方法去解决。