暴力递归

暴力递归是什么？

暴力递归就是尝试

1、把问题转化为规模缩小了的同类问题的子问题 2、有明确的 不需要继续 进行递归的条件（base case） 3、有当得到了子问题的结果之后决策过程 4、不记录每一个子问题的解（这一步是暴力尝试，所以优化放在后面）

注意！！！递归只能以递归的思路理解，把它展开纯属自讨苦吃。

汉诺塔问题 ⭐

打印 n 层汉诺塔从左边移动到最右边的全部过程

汉诺塔是根据一个传说形成的数学问题，有三根杆子A，B，C。A杆上有 n 个 (n>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

(1)每次只能移动一个圆盘； (2)大盘不能叠在小盘上面。

提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

如图，从左边移动到右边的整个步骤

步骤

最终的目的都是将 A 柱子上最下面的盘子移到 C 柱子上，最下面的盘子也就是第 n 个盘子，那么要移动第 n 个盘子，我们要确保两个条件成立：

第一个：A 柱子只剩下第 n 个盘子； 第二个：C 柱子上没有盘子（或者换一种说法就是除了第 n 个盘子留在 A 柱子外，其余的 n-1 个盘子全部移到 B 柱子上）

具体参考这个回答：

如何理解汉诺塔的递归？ - invalid s的回答 - 知乎 核心！！！！！！！ 又开始不理解递归了就看看

具体代码实现：

public class Hanoi {
  public static void hanoi(int n) {
    if (n > 0) {
      // 这里左右中表示从 左出发到右，中是另外一个
      func(n, "左", "右", "中");
    }
  }

  /**
   * 1~i 圆盘目标是 from -> to，other 是另一个（总共三个柱子）
   */
  public static void func(int i, String start, String end, String other) {
    // ②
    if (i == 1) { // base case 当只剩下最后一个盘子时，把盘子移到目标位置
      System.out.println("Move 1 from " + start + " to " + end);
    }
    else {
      // ①
      // 先把 i - 1 全部盘子移动到中间
      func(i - 1, start, other, end);
      System.out.println("Move " + i + " from " + start + " to " + end);
      // ③
      // 再把 i - 1 的全部盘子移动到右边
      func(i - 1, other, end, start);
    } 
  }

  public static void main(String[] args) {
    int n = 64;
    hanoi(n);
  }
}

如上，实际就只做三步 ① 把整个 n - 1 的搬到中间 ② 把最后一个移动到目标位置 ③ 把整个 n - 1 的搬到目标位置

打印全部子序列

打印一个字符串的全部子序列，包括空字符串

如图，每个字符都有两个选择，要或者不要，根据要或者不要最终打印叶子节点

public class NanDaoPrintAllSubs {
 
    public static void main(String[] args) {
        String test = "abc";
        List<String> ans1 = subList(test);
 
        //如果打印非重复子序列，可用数据结构
       // HashSet<String> ans1 = new HashSet<>();
        for(String ans :  ans1){
            System.out.println(ans);
        }
        System.out.println("=========");
    }
 
    private static List<String> subList(String test) {
        //转换成字符数组
        char[] str = test.toCharArray();
        String path = " ";
        List<String> ans = new ArrayList<>();
        process(str,0,ans,path);
        return ans;
 
    }
 
    private static void process(char[] str, int index, List<String> ans, String path) {
        if(index == str.length){
            // 把所有生成的子序列，放入到ans里去
            ans.add(path);
            return;
        }
        // 没有要index + 1位置的字符
        process(str,index + 1,ans,path);
 
        // 要了index + 1位置的字符
        process(str,index + 1,ans,path + str[index]);
    }
 
}

取得全部子字串

注意，这里取的是字串，不是序列，子序列可以是不连续的，但子串一定是连续的。

func main() {
  ans1 := make(map[string]struct{})
	println(process("1AB2345CD"， ans1))
}

func process(str string, ans map[string]struct{}) {
	for i := 0; i < len(str); i++ {
		for j := i; j < len(str); j++ {
			ans[str[i:j + 1]] = struct{}{}
		}
	}
}

不同于上面，这里是按顺序取得全部子字串