请添加图片描述

⭐️前言⭐️

本篇文章分享一些常见的递归题目，为后边的动态规划篇章做铺垫。

🍉欢迎点赞 👍 收藏 ⭐留言评论 📝私信必回哟😁

🍉博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

🍉博客中涉及源码及博主日常练习代码均已上传GitHub

请添加图片描述

📍内容导读📍

🍅汉诺塔
🍅字符串的全部子序列
🍅字符串的全部子序列（去重）
🍅字符串的全排列
🍅字符串的全排列（去重）
🍅逆序栈

🍅汉诺塔

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

题解思路：
若想把n层汉诺塔从最左边移到最右边，分为以下三大步：
首先把1~n-1层从最左边移到中间，
然后把第n层从最左边移到最右边，
最后再把1~n-1层从中间移到最右边。

移动可以拆分成六个方向，来去嵌套完成递归，如下所示：
代码实现：

public class Hanoi {public static void hanoi1(int n) {leftToRight(n);}// 请把1~N层圆盘   从左->右public static void leftToRight(int n) {if(n==1) {  // base caseSystem.out.println("Move 1 from left to right");return;}leftToMid(n-1);System.out.println("Move "+n+" from left to right");midToRight(n-1);}public static void leftToMid(int n) {if(n==1) {System.out.println("Move 1 from left to mid");return;}leftToRight(n-1);System.out.println("Move "+n+" from left to mid");rightToMid(n-1);}public static void rightToMid(int n) {if(n==1) {System.out.println("Move 1 from right to mid");return;}rightToLeft(n-1);System.out.println("Move "+n+" from right to mid");leftToMid(n-1);}public static void rightToLeft(int n) {if(n==1) {System.out.println("Move 1 from right to left");return;}rightToMid(n-1);System.out.println("Move "+n+" from right to left");midToLeft(n-1);}public static void midToLeft(int n) {if(n==1) {System.out.println("Move 1 from mid to left");return;}midToRight(n-1);System.out.println("Move "+n+" from mid to left");rightToLeft(n-1);}public static void midToRight(int n) {if(n==1) {System.out.println("Move 1 from mid to right");return;}midToLeft(n-1);System.out.println("Move "+n+" from mid to right");leftToRight(n-1);}public static void main(String[] args) {int n=3;hanoi1(3);}
}

但其实三个位置，再进一步抽象可以成为from、to和other，实现代码如下：

 public static void hanoi2(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) {System.out.println("Move 1 from "+from+" to "+to);}else {func(n-1,from,other,to);System.out.println("Move "+n+" from "+from+" to "+to);func(n-1,other,to,from);}}

🍅字符串的全部子序列

题目：
打印一个字符串的全部子序列
题解思路：
字符串的每个位置只需判断要或者不要即可，传递参数path用于存储每个位置的取舍情况，把每种情况记录即为结果。

代码实现：

public class PrintAllSubsequences {// s -> "abc" ->public static List<String> subs(String s) {char[] str=s.toCharArray();String path="";List<String> ans=new ArrayList<>();process(str,0,ans,path);return ans;}// str固定参数// str[0...index-1]已经走过了，都在path上// str[index...]之后还可以决定// 把所有生成的子序列，放入到ans中public static void process(char[] str, int index, List<String> ans, String path) {if(index== str.length) {ans.add(path);return;}// 没有要index位置的字符process(str,index+1,ans,path);process(str,index+1,ans,path+String.valueOf(str[index]));}public static void main(String[] args) {String test="abc";List<String> ans=subs(test);for(String s:ans) {System.out.println(s);}}
}

🍅字符串的全部子序列（去重）

题目：
打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
题解思路：
与上题思路相同，只是换为set集合存储path即可完成去重。

代码实现：

public class PrintAllSubsequences {public static List<String> subsNoRepeat(String s) {char[] str=s.toCharArray();String path="";HashSet<String> set=new HashSet<>();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) {set.add(path);return;}process2(str,index+1,set,path);process2(str,index+1,set,path+String.valueOf(str[index]));}public static void main(String[] args) {String test="accc";List<String> ans=subsNoRepeat(test);for(String s:ans) {System.out.println(s);}}
}

🍅字符串的全排列

https://leetcode.cn/problems/permutations/
题目：
打印一个字符串的全部排列

代码实现：

class Solution {List<List<Integer>> res=new LinkedList<>();// 主函数，输入一组不重复的数字，返回他们的全排列。public List<List<Integer>> permute(int[] nums) {//记录路径LinkedList<Integer> track=new LinkedList<>();//路径中的元素会被标记为true,避免重复使用boolean[] used=new boolean[nums.length];backtrack(nums,track,used);return res;}// 路径记录在track中// 选择列表：nums中不存在于track的那些元素// 结束条件：nums中的元素全都在track中出现void backtrack(int[] nums,LinkedList<Integer> track,boolean[] used) {//触发结束条件if(track.size()==nums.length) {res.add(new LinkedList(track));return;}for(int i=0;i<nums.length;i++) {// 排除不合法的选择if(used[i]) continue;// 做选择track.add(nums[i]);used[i]=true;backtrack(nums,track,used);// 取消选择used[i]=false;track.removeLast();}}
}

🍅字符串的全排列（去重）

https://leetcode.cn/problems/permutations-ii/description/
题目：
打印一个字符串的全部排列，要求不要出现重复的排列

代码实现：

class Solution {List<List<Integer>> res=new LinkedList<>();// 主函数，输入一组不重复的数字，返回他们的全排列。public List<List<Integer>> permute(int[] nums) {//记录路径LinkedList<Integer> track=new LinkedList<>();//路径中的元素会被标记为true,避免重复使用boolean[] used=new boolean[nums.length];backtrack(nums,track,used);return res;}// 路径记录在track中// 选择列表：nums中不存在于track的那些元素// 结束条件：nums中的元素全都在track中出现void backtrack(int[] nums,LinkedList<Integer> track,boolean[] used) {//触发结束条件if(track.size()==nums.length) {res.add(new LinkedList(track));return;}for(int i=0;i<nums.length;i++) {// 排除不合法的选择if(used[i]) continue;// 做选择track.add(nums[i]);used[i]=true;backtrack(nums,track,used);// 取消选择used[i]=false;track.removeLast();}}
}

🍅逆序栈

题目：
给定一个栈，请逆序这个栈，不能申请额外的数据结构，只能使用递归函数
代码实现：

public class ReverseStack {public static void reverse(Stack<Integer> stack) {if(stack.isEmpty()) {return;}int i=f(stack);reverse(stack);stack.push(i);}// 栈底元素移除// 上面的元素盖下来// 返回移除掉的栈底元素public static int f(Stack<Integer> stack) {int result=stack.pop();if(stack.isEmpty()) {return result;}else {int last=f(stack);stack.push(result);return last;}}
}