【算法&数据结构体系篇class17】：递归

谁践踏了优雅 2024-03-25 17:14 15阅读 0赞

### 一、暴力递归 ###

> **暴力递归就是尝试**   
> 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<String> subs(String s){
            char[] str = s.toCharArray();      //字符串转换成字符数组
            String path = "";                  //初始化 选择的字符路径
            List<String> 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<String> 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<String> subsNoRepeat(String s){
            char[] str = s.toCharArray();              //转换字符数组处理
            HashSet<String> set = new HashSet<>();     //定义有序表存储数据去重 重复不保存
            String path = "";                          //已选字符路径
            process2(str,0,set,path);
            List<String> ans = new ArrayList<>();
            for(String ss: set){
                ans.add(ss);
            }
            return ans;
        }
        public static void process2(char[] str,int index, HashSet<String> set,String path){
            if(index == str.length){
                //base case:如果索引越界了就将当前path加入set中
                set.add(path);
                return;
            }
            //递归遍历 当前index不取字符 path保持上层不变 index+1
            process2(str,index+1,set,path);
            //递归遍历 当前index取字符  path加上当前字符 index+1
            process2(str,index+1,set,path+str[index]);
        }
    
    
        public static void main(String[] args) {
            String test = "acc";
            List<String> ans1 = subs(test);
            List<String> 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
     * <p>
     * 打印一个字符串的全部排列，要求不要出现重复的排列
     * "acc"  acc cac cca    如果不去重 因为存在相同字符两个c就会有相同的排序结果
     */
    public class PrintAllPermutations {
        //打印一个字符串的全部排列  方法一
        public static List<String> permutation1(String s) {
            //定义一个结果集合
            List<String> ans = new ArrayList<>();
            if (s == null || s.length() == 0) {
                //字符串空 直接返回空集合
                return ans;
            }
            //定义一个集合保存每个字符
            List<Character> list = new ArrayList<>();
            char[] chars = s.toCharArray();
            for (char c : chars) {
                list.add(c);
            }
            //定义一个访问路径
            String path = "";
            //调用递归函数  返回全部的排列给ans
            f(list, path, ans);
            return ans;
        }
    
        /**
         * @param list 字符集合 每次选后就进行删除 最后回到该层递归就要在复原
         * @param path 访问过的字符路径
         * @param ans  将访问过的字符路径转换字符串保存到结果集中
         */
        public static void f(List<Character> list, String path, List<String> 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);
                //接着递归下层 路径加上当前来到的字符ch
                f(list, path + ch, ans);
                //当我们首次 遍历得到的就是原字符顺序 开始返回上层调用 需要将当前层删除的元素 对应索引去恢复元素内容 不然会存在有些字符顺序缺失
                list.add(i, ch);
            }
        }
    
        //打印一个字符串的全部排列 方法二
        public static List<String> permutation2(String s) {
            //定义一个结果集合
            List<String> ans = new ArrayList<>();
            if (s == null || s.length() == 0) {
                //字符串空 直接返回空集合
                return ans;
            }
            //转换字符数组
            char[] chars = s.toCharArray();
            //调用递归 从索引0开始递归遍历字符数组 返回全部排列ans
            g(chars, 0, ans);
            return ans;
        }
    
        public static void g(char[] ch, int index, List<String> 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<String> permutation3(String s) {
            //定义一个结果集合
            List<String> 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<String> 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<String> ans1 = permutation1(s);
            for (String str : ans1) {
                System.out.println(str);
            }
            System.out.println("=======");
            List<String> ans2 = permutation2(s);
            for (String str : ans2) {
                System.out.println(str);
            }
            System.out.println("=======");
            List<String> 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<Integer> 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<Integer> stack){
            //弹出当前栈顶元素
            int res = stack.pop();
            //如果此时栈空了 那么就将前面弹出的元素返回上层调用
            if(stack.isEmpty()){
                return res;
            }
            //递归调用，直到栈空，返回栈底元素 保存 用来返回上层结果
            int last = f(stack);
            //首次来到栈空位置，入栈的是原栈的倒数第二个元素 最后一个元素在前面已经弹出 并且保存在last
            stack.push(res);
            //返回上层 带上栈底元素，依次返回到顶部 返回都是栈底元素
            return last;
        }
    
    
        public static void main(String[] args) {
            Stack<Integer> test = new Stack<Integer>();
            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());
            }
    
        }
    }