复习：递归

递归有两个特点：

• 调用自身
• 结束条件

• 左上：死递归，没有结束条件
• 右上：合法递归，比方说x=3，永远不会结束
• 左下：不合法
• 右下：合法

  注意：fun3是先打印后递归，所以如果传入3，打印321 fun4先递归后打印，所以如果传入3，打印123

汉诺塔问题

思路：上面n-1个盘子堪称一个整体，最后是最大1个盘子

代码：

package com.algorithm.demo;
/**
* @Author leijs
* @date 2022/4/9
*/
public class Hanoi {
    static int i = 0;
    public static void main(String[] args) {
        // 从A经过B挪到C
        // a->c， a->b, b->c
        hanoi(64, "A", "B", "C");
        System.out.println(i);
    }
    public static void hanoi(int n, String a, String b, String c) {
        if (n > 0) {
            hanoi(n-1, a, c, b);
            //            System.out.println(String.format("moving from %s to %s", a,c));
            i++;
            hanoi(n-1, b, a, c);
        }
    }
}