一、暴力递归

暴力递归就是尝试
1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件(basecase)
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解

二、熟悉什么叫尝试

•打印n层汉诺塔从最左边移动到最右边的全部过程
•
•打印一个字符串的全部子序列
•
•打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
•
•打印一个字符串的全部排列
•
•打印一个字符串的全部排列，要求不要出现重复的排列

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

package class17;/*** 打印n层汉诺塔从最左边移动到最右边的全部过程*  汉诺塔，左中右 三个棍子，一开始左侧放着一堆环，从上到下依次环变大放着 要求从将这个顺序环移动到右侧棍子 移动过程还要遵守小环在大环上面*/public class Hanoi {//方法一 汉诺塔调用递归函数 一共有六个递归函数。左到中 左到右  中到左 中到右 右到左 右到中/*** 宏观考虑：* 左->右：* 1.将顶部n-1个环 从左移动到中  再将下面第n个环 打印输出移动顺序：n从左移动到右，再将n-1个环从中移动到右* 这里涉及  左->中  中->右 两个递归函数** 左->中：* 1.将顶部n-1个环 从左移动到右  再将下面第n个环 打印输出移动顺序：n从左移动到中，再将n-1个环从右移动到中* 这里涉及  左->右  右->中 两个递归函数...***/public static void hannoi1(int n){//调用左移动到右的递归函数leftToRight(n);}// 请把1~N层圆盘 从左 -> 右public static void leftToRight(int n){//停止递归的条件 base case 层数只剩1层 可以直接从左侧移动到右侧 直接打印 1 从左移动到右，然后退出当前递归if(n == 1){System.out.println("Move 1 from left to right");return;}//先将顶部n-1个环移动到中间leftToMid(n-1);//移动完后，将最底部第n个环从左移动到右 打印出来 因为只剩一个环 直接移动System.out.println("Move "+ n + " from left to right");//最后就是将n-1个环 从中间再移动到右边midToRight(n-1);}// 请把1~N层圆盘 从左 -> 中public static void leftToMid(int n){if(n == 1){//n只有1个环 直接打印从 1环 左->中System.out.println("Move 1 from left to mid");return;}//先将顶部n-1个环从左移动到右侧leftToRight(n-1);//移动完成 左侧只剩一个环，直接打印 左->中System.out.println("Move "+n+" from left to mid");//最后再将右侧的n-1个环移动到中间rightToMid(n-1);}// 请把1~N层圆盘 从中 -> 右public static void midToRight(int n){if(n == 1){//n只有1个环 那就直接打印中->右 只剩一个环可以直接移动System.out.println("Move 1 from mid to right");return;}//先将中间 顶部n-1个环移动到左midToLeft(n-1);//移动完中间剩下底部第n个环 直接打印输出 n 从中间->右System.out.println("Move " + n + " from mid to right");//最后再将中间n-1个环 移动到右边leftToRight(n-1);}// 请把1~N层圆盘 从中 -> 左public static void midToLeft(int n){if(n == 1){//一个环 直接打印 1 中->左System.out.println("Move 1 from mid to left");return;}//先将中间 顶部n-1个环 移动到右midToRight(n-1);//移动完中间就是底部第n个环 直接打印 中-> 左System.out.println("Move " + n + " from mid to left");//然后最后将右边n-1个环移动到左边rightToMid(n-1);}// 请把1~N层圆盘 从右 -> 中public static void rightToMid(int n){if(n == 1 ){System.out.println("Move 1 from right to mid");return;}//先将右侧 顶部n-1个环 移动到左边rightToLeft(n-1);//然后右侧只剩最后一个n环 直接打印输出 右->中System.out.println("Move " + n + " from right to mid");//最后将左边的n-1个环移动到中间leftToMid(n-1);}// 请把1~N层圆盘 从右 -> 左public static void rightToLeft(int n){if(n==1){System.out.println("Move 1 from right to left");return;}//先将右侧 顶部n-1个环移动到中间rightToMid(n-1);//移动完 右侧就只剩最后n环，直接打印移动 右->左System.out.println("Move " + n + " from right to left");//最后再将中间n-1个环移动到左边midToLeft(n-1);}/*** 方法二： 只用一个递归函数  压缩递归函数，给递归函数加四个参数N(多少层)  from to other 表示三个汉诺塔的棍 从那里from*         移动到那里to  然后第三棍就是other* @param n*/public static void hannoi2(int n){if(n > 0){func(n,"left","right","mid");}}//递归函数public static void func(int n,String from,String to,String other){if(n == 1){//base case:当n为一个环时，则可以直接打印输出 将1  从 from 左边 移动到to 右边System.out.println("Move 1 from "+from + " to " + to);return;}//先将from位置也就是左边 顶部n-1个环 移动到other位置 中间 ； 注意这里第二个参数移动到other mid中间 而第三个参数就是to 右边func(n-1,from,other,to);//移动完之后 from位置 也就是左边 剩下一个环 底部N 只有一个可以直接打印输出System.out.println("Move "+ n +" from " + from + " to "+to);//最后再将在other位置 中间的n-1个环移动到 to 右边位置, 这个时候第三参数 其他棍就是from 右边func(n-1,other,to,from);}public static void main(String[] args){int n = 3;hannoi1(3);System.out.println("============");hannoi2(3);}
}

2.2 打印一个字符串的全部子序列 / 以及要求不要出现重复字面值的全部子序列

package class17;import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;/*** 打印一个字符串的全部子序列*比如： "ab"   全部子序列是  ""  a ab b  (空也算一个)** 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列* 去重比如 "acc"  如果不去重 两个c就会认为不一样 会有 ac 索引1的c  ac 索引2的c* 基于第一种 采用有序表接收 即可去重*/
public class PrintAllSubsquences {//打印字符串的全部子序列public static List subs(String s){char[] str = s.toCharArray();      //字符串转换成字符数组String path = "";                  //初始化 选择的字符路径List ans = new ArrayList<>();  //存放全部子序列结果//递归函数 传递字符串 ， 开始遍历的字符索引，结果集，访问的当前字符路径process1(str,0,ans,path);return ans;}/**** @param str  字符数组内容* @param index 字符数组索引* @param ans   保存子序列* @param path  以访问过的字符路径*/public static void process1(char[] str,int index,List ans,String path){if(index == str.length){//base case: 如果遍历字符数组索引到了最后越界，就将当前的path添加到ans结果集中 返回上层ans.add(path);return;}//递归遍历 如果当前index索引字符内容不选择，即该索引字符不选 为空。 那么就继续递归。index+1下个索引，路径以及传递上层的path不变process1(str,index+1,ans,path);//递归遍历 如果当前index索引字符内容选择 即该索引字符选 则str[index]追加path，并递归下个索引process1(str,index+1,ans,path+ str[index]);}//打印一个字符串的全部子序列，要求不要出现重复字面值的子序列public static List subsNoRepeat(String s){char[] str = s.toCharArray();              //转换字符数组处理HashSet set = new HashSet<>();     //定义有序表存储数据去重 重复不保存String path = "";                          //已选字符路径process2(str,0,set,path);List ans = new ArrayList<>();for(String ss: set){ans.add(ss);}return ans;}public static void process2(char[] str,int index, HashSet set,String path){if(index == str.length){//base case:如果索引越界了就将当前path加入set中set.add(path);return;}//递归遍历 当前index不取字符 path保持上层不变 index+1process2(str,index+1,set,path);//递归遍历 当前index取字符  path加上当前字符 index+1process2(str,index+1,set,path+str[index]);}public static void main(String[] args) {String test = "acc";List ans1 = subs(test);List ans2 = subsNoRepeat(test);for (String str : ans1) {System.out.println(str);}System.out.println("=================");for (String str : ans2) {System.out.println(str);}System.out.println("=================");}}

2.3  打印一个字符串的全部排列 / 以及要求不要出现重复的全部排列

package class17;import java.util.ArrayList;
import java.util.List;/*** 打印一个字符串的全部排列* "abc" ->   abc acb bac bca cba cab* 
* 打印一个字符串的全部排列，要求不要出现重复的排列* "acc"  acc cac cca    如果不去重 因为存在相同字符两个c就会有相同的排序结果*/
public class PrintAllPermutations {//打印一个字符串的全部排列  方法一public static List permutation1(String s) {//定义一个结果集合List ans = new ArrayList<>();if (s == null || s.length() == 0) {//字符串空 直接返回空集合return ans;}//定义一个集合保存每个字符List list = new ArrayList<>();char[] chars = s.toCharArray();for (char c : chars) {list.add(c);}//定义一个访问路径String path = "";//调用递归函数  返回全部的排列给ansf(list, path, ans);return ans;}/*** @param list 字符集合 每次选后就进行删除 最后回到该层递归就要在复原* @param path 访问过的字符路径* @param ans  将访问过的字符路径转换字符串保存到结果集中*/public static void f(List list, String path, List ans) {if (list.isEmpty()) {//当字符集合都已经遍历完 就将当前路径添加到ans 再返回上层调用ans.add(path);return;}//全部排列 每个字符都可以尝试做第一个元素排列 遍历整个字符集合for (int i = 0; i < list.size(); i++) {//取出当前来到的字符 删除Character ch = list.get(i);list.remove(i);//接着递归下层 路径加上当前来到的字符chf(list, path + ch, ans);//当我们首次 遍历得到的就是原字符顺序 开始返回上层调用 需要将当前层删除的元素 对应索引去恢复元素内容 不然会存在有些字符顺序缺失list.add(i, ch);}}//打印一个字符串的全部排列 方法二public static List permutation2(String s) {//定义一个结果集合List ans = new ArrayList<>();if (s == null || s.length() == 0) {//字符串空 直接返回空集合return ans;}//转换字符数组char[] chars = s.toCharArray();//调用递归 从索引0开始递归遍历字符数组 返回全部排列ansg(chars, 0, ans);return ans;}public static void g(char[] ch, int index, List ans) {if (index == ch.length) {//当遍历的索引越界 遍历完成 就将当前字符数组转换加入结果集合ans.add(String.valueOf(ch));return;}for (int i = index; i < ch.length; i++) {//进行字符数组的顺序交换 以达变化以每个字节做开始的全部排序序列swap(ch, i, index);//接着递归下一个索引字符g(ch, index + 1, ans);//最后一层遍历完得到一个结果，要返回上层继续调用 先恢复当前的交换位置字符swap(ch, i, index);}}public static void swap(char[] ch, int i, int j) {char temp = ch[i];ch[i] = ch[j];ch[j] = temp;}//打印一个字符串的全部排列  要求不要出现重复的排列//增加一个 布尔数组 判断是否已经重复的排列就跳过 剪枝操作public static List permutation3(String s) {//定义一个结果集合List ans = new ArrayList<>();if (s == null || s.length() == 0) {//字符串空 直接返回空集合return ans;}//转换字符数组char[] chars = s.toCharArray();//调用递归函数 从0索引开始遍历 返回ans全部去重排列h(chars, 0, ans);return ans;}public static void h(char[] ch, int index, List ans) {if (index == ch.length) {//越界 将当前字符数组转换加入集合 返回上层调用ans.add(String.valueOf(ch));return;}//定义一个布尔数组判断是否有重复排列 有则不进行该层递归 剪枝操作//ASCII字符表 一个字符最多表示256个字符boolean[] visited = new boolean[256];for (int i = index; i < ch.length; i++) {//ch[i]字符如果有重复的 对应的布尔数组中就是同一位置 没有访问过就执行逻辑 访问过了就会跳过 剪枝 避免重复if (!visited[ch[i]]) {//当该字符没有被取出时，进行逻辑，修改访问值true. 进行交换操作 往下个索引递归//比如acc字符串  str[1]第一个c 取到之后得到cac cca两个排序 到第二c str[2] 如果继续做判断遍历//就会又新增 cac cca 所有需要visited判断有相同字符 不再重复遍历 这样就不会重复排序出现visited[ch[i]] = true;swap(ch, i, index);h(ch, index + 1, ans);//最后返回上层 需要恢复现场 原数组顺序swap(ch, i, index);}}}public static void main(String[] args) {String s = "acc";List ans1 = permutation1(s);for (String str : ans1) {System.out.println(str);}System.out.println("=======");List ans2 = permutation2(s);for (String str : ans2) {System.out.println(str);}System.out.println("=======");List ans3 = permutation3(s);for (String str : ans3) {System.out.println(str);}}
}

三、给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。 如何实现?

package class17;import java.util.Stack;/*** 给你一个栈，请你逆序这个栈，* 不能申请额外的数据结构，* 只能使用递归函数。 如何实现?** 思路* 1.设计一个递归函数f，将栈底移除 然后上层元素依次往下压 同时返回移除的哪个原栈底元素* 2.然后外层函数，套进这个f函数，并且外层也是递归，一直是将栈底部返回并且移除。直到最后* 移除到空，就开始往上调用 依次push 前面移除的元素这样栈的顺序就会倒序*/
public class ReverseStackUsingRecursive {//将栈倒序 利用递归  不使用额外数据结构public static void reverse(Stack stack){//递归弹出栈直到空时就直接返回上层if(stack.isEmpty()) return;//调用f函数，移除并返回栈底元素int i = f(stack);//移除后就接着递归调用该倒序函数 直到栈空reverse(stack);//直到栈空了 那么就来到往上调用，依次当前移除的栈底元素 再重新依次入栈//比如一开始入栈 1 2 3  那么到这里第一次是栈空 3入栈 再上层 2入栈 1入栈//栈就变成 3 2 1 倒序了stack.push(i);}//将栈底部元素返回并移除public static int f(Stack stack){//弹出当前栈顶元素int res = stack.pop();//如果此时栈空了 那么就将前面弹出的元素返回上层调用if(stack.isEmpty()){return res;}//递归调用，直到栈空，返回栈底元素 保存 用来返回上层结果int last = f(stack);//首次来到栈空位置，入栈的是原栈的倒数第二个元素 最后一个元素在前面已经弹出 并且保存在laststack.push(res);//返回上层 带上栈底元素，依次返回到顶部 返回都是栈底元素return last;}public static void main(String[] args) {Stack test = new Stack();test.push(1);test.push(2);test.push(3);test.push(4);test.push(5);reverse(test);while (!test.isEmpty()) {System.out.println(test.pop());}}
}