前言
搜索是算法学习者经常会用的一种算法，本质上是暴力算法的一种优化。我们在初期经常会用到BFS和DFS。今天我们来学习DFS。

什么是递归
简单来说，就是函数自己调用自己。因为函数在运行过程中产生的数据通常是存放在栈中的，所以它可以在递归开始返回后将最后一次入栈的数据出栈，再回到上一个程序。来看一个具体的例子：

本题很简单，但是也可以不用循环做，可以使用递归：

#include <bits/stdc++.h>

int times(int n){//递归程序
    if(n==1) return 1;
    else return n*times(n-1);//自己调用自己
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d",times(n));
    return 0;
}

这里程序在函数中不断调用自己，直到n=1时开始回归，巧妙的实现了从1乘到n。
需要注意的是，递归在使用过程中会有损耗，故在时间复杂度相同时会慢于普通循环。

程序设计思路
首先我们要明白搜索都是基于树论的。你想要使用搜索，就必须先自己构造出一棵树。

如上图所示，就是一棵树的图形表示。
与BFS不同，DFS的原则是“不撞南墙不回头”，因此如果使用DFS对上面的树进行搜索，顺序应该是：2→7→1→6→5→3→8→9→4。
由于图片中展示的是一棵二叉树，而实际问题中树的子树数量不是固定的，所以通常会使用递归的方式写程序。

代码实现
下面是一个例子：

这是一道典型的DFS的题目。在这题中，由于两个皇后肯定不会在同一行，我们可以对每一行可能出现的情况进行枚举，再进行判断。于是问题就变成了要遍历n棵n叉树并判断。下面是代码——

#include <bits/stdc++.h>
using namespace std;

int n,ans=0,out[14];//ans用于累加，out数组存放要输出的答案
bool flag;//用于记录是否有答案

void dfs(int step){//step为行数
    if(step>n){//出口程序
        ans++;
        if(ans<=3){//输出前三个答案
            for(int i=1;i<=n;i++) printf("%d ",out[i]);
            printf("\n");
        }
    }
    for(int i=1;i<=n;i++){
        flag=true;//初始化flag
        for(int j=1;j<step;j++) if(out[j]==i || abs(i-out[j])==step-j){//前一个条件判断纵向，后一个条件判断是否处于同一45°角上。
            flag=false;//当不满足条件时，将答案标记为错误并直接跳出循环不再判断（剪枝）
            break;
        }//用之前放置的所有皇后进行判断
        if(!flag)continue;//当答案不正确时，进入下一循环
        out[step]=i;//存下答案
        dfs(step+1);//进行下一层判断
    }
    return ;
}

int main(){
    scanf("%d",&n);
    dfs(1);
    printf("%d",ans);
    return 0;
}

这里我们使用递归不断调用自己，达到一个函数搞定的效果。再来看一个例子：

这题也是经典的地图搜索题，上代码：

#include <bits/stdc++.h>

int r,c,n,a,b,iq[1010];//r、c、n如题意，a、b用来存放起点坐标，iq[i]为第i次操作的方向编号（1、2、3、4分别代表东、南、西、北）
char Map[55][55],input[6];//Map用于存地图，input用来输出操作的内容
bool ans[55][55],flag[55][55][1010];//ans存放能否到达坐标对应点，flag[i][j][k]存放是否在第k步到达(i,j)（记忆化）
void dfs(int num,int x,int y){//num代表递归层数，x、y代表要进行搜索的坐标
    if(flag[x][y][num]) return ;//如果当前点已经算过则返回
    if(num>=n){//当层数大于步数时退出计算
        ans[x][y]=true;
        return ;
    }//以下为分类讨论
    int i=x,j=y;
    if(iq[num]==1) while(1){//当下一步向东走时，横坐标不断加1直到超界或撞墙
        j++;//一步一步走
        if(j>=c || Map[x][j]=='X') break;//判断超界或撞墙
        dfs(num+1,x,j);//计算下一步
    }
    if(iq[num]==2) while(1){//同上
        i++;
        if(i>=r || Map[i][y]=='X') break;
        dfs(num+1,i,y);
    }
    if(iq[num]==3) while(1){//同上
        j--;
        if(j<0 || Map[x][j]=='X') break;
        dfs(num+1,x,j);
    }
    if(iq[num]==4) while(1){//同上
        i--;
        if(i<0 || Map[i][y]=='X') break;
        dfs(num+1,i,y);
    }
    flag[x][y][num]=true;//将当前位置标记为已走过
    return ;
}

int main(){
    scanf("%d%d",&r,&c);
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) ans[i][j]=false;
    for(int i=0;i<r;i++) scanf("%s",Map[i]);
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) if(Map[i][j]=='*'){
        a=i;
        b=j;
    }
    scanf("%d",&n);
    for(int i=0;i<r;i++) for(int j=0;j<c;j++) for(int k=0;k<n;k++) flag[i][j][k]=false;
    for(int i=0;i<n;i++){//每读入一个操作就转义为数字操作编号
        scanf("%s",input);
        if(input[0]=='E') iq[i]=1;
        if(input[0]=='S') iq[i]=2;
        if(input[0]=='W') iq[i]=3;
        if(input[0]=='N') iq[i]=4;
    }
    dfs(0,a,b);//从(a,b)出发
    for(int i=0;i<r;i++){//输出
        for(int j=0;j<c;j++){
            if(Map[i][j]=='X') printf("X");
            else if(ans[i][j]) printf("*");//如果该点可以到达，输出'*'
            else printf(".");
        }
        printf("\n");
    }
    return 0;
}

这题要我们对地图进行计算，还是很好理解的。这里我加上了记忆化，效率更高。

DFS的优化——剪枝
剪枝，顾名思义，就是通过程序方法直接排除一些子树，以求提高效率。主要分为可行性剪枝和奇偶性剪枝。
可行性剪枝，就是从题目意义上将某些不可能的情况排除。比如说，要计算一个人能不能在规定时间刚刚好走到某个格子（路线不能重复），如果你在搜索的过程中碰到一种情况：这张地图上所有格子的总数比单位时间内可以走的路程还要少，那根本就不用算了，直接false！
还有一种奇偶性剪枝。我们可以将一张地图看成这样：
0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

1 0 1 0 1 0 1 0
在这张图上，从0走到1或从1走到0肯定要奇数步，从0走到0或从1走到1肯定要偶数步。所以如果碰到这种平面图算步数的搜索题也可以直接用奇偶性pass一部分。
剪枝的具体代码可以是多样化的，但是其中心目的只有一个——减少搜索量。

记忆化DFS
DFS在调用的递归嵌套过多时会爆栈，因此我们可以为其加上记忆化以防超界。记忆化是指在一棵树中，可能会有重复的子树，导致重复计算，所以我们可以使用数组将一种情况记录下来，下次再碰到这个情况直接跳过计算，以减少调用。
记忆化DFS是一种以更高的空间复杂度换取更低的时间复杂度的方法。当代码面临TLE时，不妨试试加上记忆化。例如上面案例中的第二题就是利用了flag数组，减少了运算量。当然，在加记忆化时也要注意空间复杂度不能过高，否则爆空间~

总结
从理论上来说，DFS和DP问题是可以互相转化的，只要学好一个，两者的问题都能解决。所以，如果你还在为了列出状态转移方程而苦恼，不妨试试用DFS的思路去思考DP问题。不过，普通的DFS容易因循环过多而爆栈，为了解决这个问题，我们需要用到优化版DFS——记忆化DFS。我是faryou，再见！