不同人眼中的递归

img

你眼中的盗梦空间：不停做梦

img

程序员眼中的盗梦空间

那什么是递归？

img

自己调用自己，最简单的一个案例就是阶乘的问题

1! = 1 | 2! = 2x1 | 3! = 3x2x1 | => f(n) = n x f(n-1) 【当n=1结束】

递归有三个需要知道

这个递归要做什么？

这个递归怎么结束？

当程序执行到一个方法时，就会开辟一个独立的空间（栈），而且其中变量互不影响

《盗梦空间》场景重现

这个递归要做什么？=> 盗梦空间中做了什么

其实做梦就是一个递归，如果睡觉/下药那么就会做梦

在梦中在睡觉/给下药 那么又做梦，目前是梦中梦

第三层在做梦，就是梦中梦中梦……

用程序可以这么表示

1
2
3
void dream(String action) {
    dream("做梦 / 下药 / 听音乐 / 猛烈撞击");
}

这样会无限做梦，电影中到第五层之后人的脑子就已经不行了，会烧坏脑子，虽然程序比人脑强上不少，可以循环很多次，但架不住它快啊，烧的比人脑还要快，最终会导致栈溢出，程序停止

所以结束条件就显得十分重要，先来看盗梦中是怎么结束的？

img

听音乐/收到猛烈撞击 会醒过来，回到上一层梦境中，那么程序就变为了这样

1
2
3
4
5
6
7
void dream(String action) {
    if ("听音乐".equals(action) || "猛烈撞击".equals(action)) {
        //返回上一层
        return;
    }
    dream("做梦 / 下药 / 听音乐 / 猛烈撞击");
}

就会开辟一个独立的空间（栈）也好理解，没有做梦空间还怎么做梦？

方法局部的变量是独立的，不会相互影响。总不能第2层做梦会影响第一层的人（当然除了死掉，不过那个算结束条件）

递归场景复现

马踏棋盘问题—一个经典的回溯问题

img

问题描述

如果给定一个m x n的棋盘，在给定一个马儿棋子的初始位置，按照马走日的规则，如何可以在每个方格只进入一次的情况下，走完整个棋盘。

当然，存在棋盘或者有些起始点不能使马儿走完整个棋盘的情况。

问题解析

马儿在任意一个点，总是会有可走的选择，如果可以走的话，选取一个点走，走不通的话就返回上一步，重新考虑下一个点进行尝试

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void DFS(int[][] act,int i, int j,int step) {
    //将马儿当前位置置为已使用，记录当前步数
    act[i][j] = step;
    if (step == act.length * act.length) {
        //如果达到预定步数，则打印，并退出程序
        print(act);
        System.exit(0);
    }
    //得到可以落子的坐标集合
    List<Luozi> ls = next(act, i, j);
    for (Luozi l : ls) {
        //递归调用可用坐标
        DFS(act,l.i,l.j,step+1);
    }
    //如果没有达到预定步数，将此点置为0，进行回溯
    if (step < act.length * act.length) {
        act[i][j] = 0;
    }
}

结果输出

1
2
3
4
5
6
19	8	11	28	17	2	
10	27	18	1	12	29	
7	20	9	30	3	16	
26	31	24	15	34	13	
21	6	35	32	23	4	
36	25	22	5	14	33

以上只提供了核心方法，如需要，源代码请到git上查看：leidl97/algorithm-src