Recursion Conclusion

How to Write a Recursive Function

Exhaustive Search 穷举搜索

递归对搜索空间进行详尽的探索，筛选符合条件的

Struct

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void explore(options, soFar)
{
    if (no more decisions to make) {
        // base case
    } else {
        // recursive case, we have a decision to make
        for (each available option) {
            choose (update options/sofar)
            explore (recur on updated options/sofar)
            unchoose (undo changes to options/sofar)
        }
    }
}

解读

  • base case 对很容易判断结果的情况做出处理，终止条件

  • recursive case

    // for each choices
    choose 对decision下的每一种choice作处理 (update decision中的结点内容)
    explore 根据自相似现象 对当前选择的choice做递归处理
    [backtracking] 每一种decision下的choices于同一级，处理完choice1再处理choice2时需要恢复到处理choice1时的状态

key Point

  1. 选择使用什么来追踪choice选择情况，并存储结果 变量or容器？
  2. 是否需要helper接口函数来添加辅助参数，该辅助参数用来存储choice选择情况
  3. Each choice如何处理 单独or循环？

Difficulty

问题决策树的绘制

Examples

排列，组合，生成子集
详细代码可见CS106B笔记对应8-10章节

注意:

并非所有递归都是该格式，一般情况是尤其是穷举搜索问题采用该格式

递归 分治 自相似

非概念性区别

递归：重复操作

分治：大问题划分为小问题，各小问题解的并集为大问题的解 是一种解决问题的思路

自相似：现象 组成部分与整体的存在形同规模不同的现象 递归时recursive部分的着手点