递归

递归方法在枚举一节中已经颇多涉及到，不过都是不带返回值的递归。本节主要阐述带返回值的递归模板，下面假设返回值是bool类型，其他类型类似。

回溯剪枝

回溯剪枝根据尝试访问的位置的不同，可以分为两种。

1、尝试访问自身：

bool search(int x) {
    if (x到达递归边界) {
        // 得到一条到边界的路径（意味着得到一个解），进行处理
        return true/false;
    }
    if (x满足剪枝条件) return true/false;

    // 尝试x，更新状态

    bool res;

    for (遍历x的所有可能后继y) {
        if (y到达递归边界) {
            // 得到一条到边界的路径（意味着得到一个解），进行处理
            continue;
        }
        if (y满足剪枝条件) continue;

        bool t = search(y); // 并用t更新res
    }

    // 还原现场

    return res;
}

bool res = search(s); // 调用search，s为状态空间根结点

2、尝试访问后继：

bool search(int x) {
    if (x到达递归边界) {
        // 得到一条到边界的路径（意味着得到一个解），进行处理
        return true/false;
    }
    if (x满足剪枝条件) return true/false;

    bool res;

    for (遍历x的所有可能后继y) {
        if (y到达递归边界) {
            // 得到一条到边界的路径（意味着得到一个解），进行处理
            continue;
        }
        if (y满足剪枝条件) continue;

        // 尝试y，更新状态
        bool t = search(y); // 并用t更新res
        // 还原现场
    }

    return res;
}

// 在此处尝试s，更新状态
bool res = search(s); // 调用search，s为状态空间根结点
// 还原现场

DFS

根据对结点进行访问操作的位置，DFS可以分为两种。

(1)访问操作自身：

bool DFS(int x) {
    if (x到达递归边界 || x满足剪枝条件) return true/false;

    // 在此处对x进行先序访问

    bool res;

    for (遍历x的所有可能后继y) {
        if (y到达递归边界 || y满足剪枝条件) continue;

        bool t = DFS(y); // 并用t更新res
    }

    // 后序访问

    return res;
}

bool res = DFS(s); // 调用DFS，从s结点开始搜索

(2)访问操作后继：

bool DFS(int x) {
    if (x到达递归边界 || x满足剪枝条件) return true/false;

    bool res;

    for (遍历x的所有可能后继y) {
        if (y到达递归边界 || y满足剪枝条件) continue;

        // 在此处对y进行先序访问
        bool t = DFS(y); // 并用t更新res
        // 后序访问
    }

    return res;
}

// 在此处对s进行先序访问
bool res = DFS(s); // 调用DFS，从s结点开始搜索
// 后序访问

注解：回溯剪枝和DFS算法框架中，判断剪枝条件、判断递归边界、进行访问操作都有两种位置，总结起来区别就是，在扩展后继之前的剪枝条件/递归边界/访问操作是针对自身的，在扩展后继之后的剪枝条件/递归边界/访问操作是针对后继的，详细可以参考枚举。

---