从递归栈到dfs

递归

绝大部分甚至全部得递归都能用循环来实现，甚至，在时间复杂度跟空间复杂度上，递归存在压栈得过程，其效率往往是不如循环得，那么为什么需要递归了，原因是相对与循环，递归逻辑更加清晰。

本质：自己调用自己

要点：递归体跟结束条件（重中之重）

斐波拉契问题：岛上第一个月存在1支兔子，十天后可以繁殖成多少对兔子?假定每对大兔每月能生产一对小兔，而每对小兔生长两个月就成为大兔

循环实现

long long fbi(int n)
{
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];
 
    int first = 0, second = 1, third = 0;
    for(unsigned int i = 2; i <= n; ++ i)
    {
        third = first + second;
        first = second;
        second = third;
    }
 
     return third;

           

递归实现

public static int fbi(int n) {
        /*
        结束条件
         */
        if (n == 0) {
            return 0;
        }
        if (n == 1)
            return 1;
        //递归体
        return fbi(n - 1) + fbi(n - 2);
    }
           

比较循环跟递归实现斐波拉契，能很明显的感受到递归相对于循环代码可读性要强很多，但递归也有缺点，在递归中，如果结束条件没有正确的写好，很容易出现死循环的情况，所以在使用递归时，必须要仔细思考结束条件。并且在递归每次都有一个压栈的过程，非常消耗时间，接下来，我们来讲解栈。

栈

栈是一种经常使用的数据结构，它的特点是先进后出，假设我们现在有一条死胡同，那条死胡同只能同时通过一个人，现在有a，b，c三人依次走进死胡同，那么如果a想从胡同中出来，只能先等c，跟b先出来，a才能出去。

下面是一道来自牛客的笔试题，大家能顺利得出答案吗？

DFS

通俗的来讲，dfs是一个常用的搜索算法，他能遍历出一个问题的所有情况，找到自己想要找到的答案，大家应该都看过复联三，奇异博士将所有情况都推到出来，发现只有一种情况才能拯救世界，当中有很多步骤，假设现在分三步，谁去抢宝石，将宝石给谁（能给自己），最后打响指，为什么不是班纳去抢宝石，因为他刚打完响指受了重伤，抢不到，所以这种情况行不通，那我们就换成蜘蛛侠，假设蜘蛛侠能抢到宝石，他先尝试打响指，蜘蛛侠发现自己无法打响指，那么这种情况也行不通，返回上一步，他想把宝石给钢铁侠，让钢铁侠打响指，结果发现时间不够，然后又返回上一步，接着他又想给其余超级英雄，结果发现都不能顺利的给他们，那么我们会蜘蛛侠抢宝石这条路走不通，我们只能换个人抢宝石，直到钢铁侠自己抢宝石，并且自己打响指，才能拯救这个世界，这是唯一解，这个有点符合dfs的思想，就是一条路走到黑，直到无路可走的情况下，才会选择回头，然后重新选择一条路。

在dfs中，最经典的就是解决迷宫问题：

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

输入

第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。

输出

能走出迷宫则输出“YES”，否则输出“NO”。

package cn.qf.javaStudy.dfs;

import java.io.FileOutputStream;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author cyf
 * @version 1.0
 */

public class Dfs {
    static ArrayList maplist = new ArrayList();
    /*
    迷宫地图
    .**
    ..*
    *..
     */
    static char[][] maze = new char[10][10];
    //标记地图上那些点已经走过，没走过为0，走过为1
    static int[][] book = new int[10][10];
    public static void main(String[] args) throws IOException {

        Scanner scanner = new Scanner(System.in);
        //迷宫的规模
        int n;
        n = scanner.nextInt();
        book[0][0] = 1;
        char s;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //输入单个字符
                maze[i][j] = (char) System.in.read();
            }
            //消除换行的影响
            s = (char) System.in.read();
        }
        //迷宫开始和结束的（x,y）坐标
        int startx, starty, endx, endy;
        startx = scanner.nextInt();
        starty = scanner.nextInt();
        endx = scanner.nextInt();
        endy = scanner.nextInt();
        dfs(n, startx, starty, endx, endy);
        FileOutputStream fileOutputStream = new FileOutputStream("D:\\a.txt");
        for (int i = 1; i <= 500; i++) {
            String ss = "你没有对象\r\n";
            fileOutputStream.write(ss.getBytes(StandardCharsets.UTF_8));

        }
        fileOutputStream.close();
    }

    private static void dfs(int n, int nowx, int nowy, int endx, int endy) {
        /*
        已经找到出口，递归结束条件，十分重要
         */
        if (nowx == endx && nowy == endy) {
            for (Object o : maplist) {
                System.out.print(o);
            }
            System.out.println();
        }
        //行走的轨迹，下、左、上、右
        int[] dx = {0, -1, 0, 1};
        int[] dy = {1, 0, -1, 0};
        int changex, changey;
        for (int i = 0; i < 4; i++) {
            changex = nowx + dx[i];
            changey = nowy + dy[i];
            //接下来走的坐标已经超出迷宫范围或者到了不能走的地方（*）
            if(changex >= n || changey>=n||changey<0||changex<0||maze[changex][changey]=='*') {
                continue;
            }
            switch (i) {
                case 0:
                    maplist.add("右");
                    break;
                case 1:
                    maplist.add("上");
                    break;
                case 2:
                    maplist.add("左");
                    break;
                case 3:
                    maplist.add("下");
                    break;
                default:
                    break;
            }
            //book为0表示没走过，如果走过再走就容易在一个地方走原路。
            if(book[changex][changey]==0){
                //走过后标记为1
                book[changex][changey]=1;
                dfs(n, changex, changey, endx, endy);
                //回溯
                book[changex][changey]=0;
            }
            //回溯
            maplist.remove(maplist.size() - 1);
        }
    }
}