递归

指在函数的定义中使用函数自身的方法
递归三要素
1. 明确递归终止条件
2. 给出递归终止时的处理办法
3. 提取重复的逻辑，缩小问题规模

java

public void recur(int level, int param) {
  	// 终止条件
  	if (level > MAX_LEVEL) {
      	return;	
      }
  
  	// 处理这一层的逻辑
  	process(level, param);
  	
  	// 进入下一层
  	recur(level + 1, newParam);
}

递归是一个隐式栈，具有后进先出的特点

回溯

利用递归的结构，对树形结构进行一遍深度优先遍历
需要借助系统栈空间 path，每层都往 path 中添加此层的状态
需要回溯：往下走一层的时候，向 path 尾部追加状态，而往回走的时候，需要撤销上一次的选择，也是在尾部操作
由于参数中的 path 是一个地址，而回溯又有撤销操作，所以在向结果 res 添加最终的 path 时，需要对 path 进行一份拷贝
中间可能能进行剪枝

java

public void dfs(Stack path, List<LIst> res) {
  	// 终止条件
  	if (level > MAX_LEVEL) {
      	// 进行一份拷贝
      	res.add(new ArrayList(path));
      	return;	
      }
  
  	// 遍历树形解某层的全部可能
  	for (int i = 0; i < n; i++) {
      	// 添加层次的结果
      	path.add(process(i));
      
      	// 进入下一层
      	dfs(path, res)
          
          // 撤回
          path.poll();
      }
}

根据题目的不同，还需要设计更多的状态变量
- 递归的终止条件是：一个排列中的数字已经选够了，因此我们需要一个变量来表示当前程序递归到第几层，我们把这个变量叫做 depth，或者命名为 index ，表示当前要确定的是某个全排列中下标为 index 的那个数是多少
- 布尔数组 used，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1)O(1) 的时间复杂度判断这个数是否被选择过，这是一种「以空间换时间」的思想

以 [1, 2, 3] 的全排列问题进行举例

先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]，即 1 + [2, 3] 的全排列
再写以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]，即 2 + [1, 3] 的全排列
最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]，即 3 + [1, 2] 的全排列
所以最后的结果为：[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

则可以归纳出一个树形结构，注意递归的顺序，是一个深度遍历

java

public List<List<Integer>> permute(int[] nums) {
      List<List<Integer>> res = new ArrayList<>();
      dfs(nums, new boolean[nums.length], new ArrayList<>(), res);
      return res;
  }

// 需要一个 used 记录哪些状态是已经遍历过的了
public void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    int n = nums.length;
    // 终止条件，当栈中有 n 个状态时，就证明已经选完了
    if (path.size() == n) {
    		// 深拷贝一份
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < n; i++) {
    		// 剪枝
        if (used[i]) continue;
        // 进行此层操作
        used[i] = true;
        path.add(nums[i]);
        // 进入下一层递归
        dfs(nums, used, path, res);
        // 撤回
        used[i] = false;
        path.remove(path.size() - 1);
    }
}

递归 ​

递归 ​

回溯 ​

递归

递归

回溯