一、什么是递归

  • 在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
  • 递归指在函数的定义中使用函数自身的方法

二、递归三要素

  • 拆解寻找子问题（得到递归规则）
  • 解决最小子问题是指可以直接得到答案问题并不需递归计算
  • 递归终止退出条件

三、递归举例

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
  • 画图
    • 根据图确定循环起始值
    • 根据图确定添加结果条件、过滤某个循环条件、终止条件
    • 根据上两点，确定递归参数
  • 套用回溯法模板