一、什么是递归
- 在数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。
- 递归指在函数的定义中使用函数自身的方法
二、递归三要素
- 拆解寻找子问题(得到递归规则)
- 解决最小子问题是指可以直接得到答案问题并不需递归计算
- 递归终止退出条件
三、递归举例
1、菲波那切数列
- 基本情况 : F(0) = 0, F(1) = 1 ,F(2) = F(0) + F(1) = 1
- 递归规则 : F(n) = F(n-1) + F(n-2)
1,1,2,3,5,8,13……
int Fibonacci (int n ){
if(n==0) return 0;
if(n==1) return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
后面用动态规划的方法或记忆搜索的方式来优化重复计算的代码。
2、汉诺塔
-
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆。规则1:每次只能移动一个圆盘;规则2:大盘不能叠在小盘上面。
-
递归规则:1. 将A上的前n-1个盘子从A移到B;2. 将第n个盘子,也就是最底下的盘子从A移到C;3. 将B上剩下的n-1个盘子从B移到C。
-
递归函数:MoveHanoi(int n, char origin, char destination, char buffer) n表示n个盘子,origin表示出发的地方,destination表示目的地,buffer表示缓存的地方。这三个char分别代表着三根杆子
代码:
public void MoveHanoi(int n,char origin,char destination,char buffer){
if(n==1){
System.out.println("Move Step:" + origin + "to" + destination);
return;
}
MoveHanoi(n-1,origin,buffer,destination);
System.out.println("Move Step:" + origin + "to" + destination);
MoveHanoi(n-1,buffer,destination,origin);
}
四、回溯法
-
什么是回溯法:回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退。回一步重新选择,这种走不通就退回再走的技术为回溯法。满足回溯条件的某个状态的点称为“回溯点”。
-
回溯法的思想:在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。
-
回溯法步骤:针对所给问题,确定问题的解空间:首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。确定结点的扩展搜索规则以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
1、回溯法模板
题目:给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子集
- 输入: nums = [1,2,3]
- 输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3],[1,2], [] ]
代码:
public List<List<Integer>> subsets(int[] nums){
// result 为解集空间
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length ==0){
return result;
}
// list为单一解
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
// 递归函数subsetHelp
subsetHelp(result,list,nums,0);
return result;
}
private void subsetHelp(List<List<Integer>> result,List<Integer>list,int[] nums,int pos){
result.add(new ArrayList<Integer>(list));
for(int i = pos;i<nums.length;i++){
list.add(nums[i]);
subsetHelp(result,list,nums,i+1);
list.remove(list.size()-1);
}
}
subsetHelp的for循环逻辑:nums=[1,2,3],对nums循环每一次循环取出1个数,然后包含该数所有的子集。取完后取第N个数,然后包含该数(排除第前N个数)的所有子集。
2、求子集
题目:给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子集
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
代码:
public List<List<Integer>> subsets(int[] nums){
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length ==0){
return result;
}
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
subsetHelp(result,list,nums,0);
return result;
}
private void subsetHelp(List<List<Integer>> result,List<Integer>list,int[] nums,int pos){
result.add(new ArrayList<Integer>(list));
for(int i = pos;i<nums.length;i++){
if(i != pos && nums[i] == nums[i-1]){
continue;
}
list.add(nums[i]);
subsetHelp(result,list,nums,i+1);
list.remove(list.size()-1);
}
}
3、全排列
题目:给定一个没有重复数字的序列,返回其所有可能的全排列。
- 输入:[1,2,3]
- 输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1],[3,1,2], [3,2,1] ]
代码:
public List<List<Integer>> subsets(int[] nums){
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length ==0){
return result;
}
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
permuteHelper(result,list,nums);
return result;
}
private void permuteHelper(List<List<Integer>> result,List<Integer>list,int[] nums){
if(list.size() == nums.length){
result.add(new ArrayList<Integer>(list));
}
for(int i = 0;i<nums.length;i++){
if(list.contains(nums[i])){
continue;
}
list.add(nums[i]);
permuteHelper(result,list,nums);
list.remove(list.size()-1);
}
}
3、组合总和
题目:给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
代码:
public List<List<Integer>> subsets(int[] candidates,int target){
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(candidates == null || candidates.length ==0){
return result;
}
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(candidates);
helper(result,list,candidates,target,0);
return result;
}
private void helper(List<List<Integer>> result,List<Integer>list,int[] candidates,int target,int pos){
if(target==0){
result.add(new ArrayList<Integer>(list));
return;
}else if(target < 0){
return;
}
for(int i = pos;i<candidates.length;i++){
list.add(candidates[i]);
helper(result,list,candidates,target-candidates[i],i);
list.remove(list.size()-1);
}
}
五、递归+回溯法+剪枝总结
- 初始化解集空间变量及类型 result
- 初始化单一解变量及类型 list
- 画图
- 根据图确定循环起始值
- 根据图确定添加结果条件、过滤某个循环条件、终止条件
- 根据上两点,确定递归参数
- 套用回溯法模板