本篇博文所有代码均用 Kotlin 进行书写，第一次出现的语法我会在注释中进行解释，不懂 Kotlin 的小伙伴也可以食用。

正向思维 OR 逆向思维

  写这篇博文的主要原因是前几天在 B站 看到了一个讲递归的视频，其中说“递归是一种逆向的思维”，我们用一个例子来介绍他的想法：

  假设我们需要求解n的阶乘，如果使用循环的写法的话代码应该是这样：

1
2
3
4
5
6
7
8
fun factorial(n: Int): Int {
    var result = 1
    // 这行代码的意思是让 i 在 [1, n] 间遍历一遍（左右均包含）
    for (i in 1..n) {
        result *= i
    }
    return result
}

  这就是平时我们写代码时用到的”正向思维“，我们的思路是先求解 1 的阶乘，然后求解 2 的阶乘……以此类推，直到求解到n的阶乘。

  但是当我们使用递归编写这段代码时却将思路反了过来，变成了想要求解n的阶乘需要先求解n - 1的阶乘，想要求解n - 1的阶乘需要先求解n - 2的阶乘……一次类推，直到变成求解 0 的阶乘时我们就可以直接返回 1，然后一层一层向上返回。具体代码为：

1
2
3
4
fun factorial(n: Int): Int {
    if (n == 0) return 1
    return factorial(n - 1) * n
}

  这么停下来这个想法好像没问题，递归确实把我们的思维反了过来，但是实际应用中我们会发现，其实很多时候递归才更符合人类的思考方式。

  总的来说，我并不完全赞同这个 UP 的观点，但同时我也不完全反对，只能说这个观点在某些情况下是成立的。

递归的作用

  那么如果递归仅有上面的作用的话似乎并没有什么存在价值，因为代码可以非常轻松地转换为循环，但是其实在实践中，大部分递归都是很难转换为循环的写法的。

  递归在求解复杂问题的时候可以起到非常重要的作用——分解复杂问题。

  简而言之，就是将一个复杂的问题分解为若干个简单的问题，其中最为典型的就是分治排序，分治排序的思想超出了我们本篇博文的范围，感兴趣的小伙伴可以去网上自行查找资料。

面向对象理解递归

  现在让我们进入本篇博文的主题——用面向对象的思想来理解递归，接下来，我们将形象的讲解递归的思路以及什么是调用栈溢出。

  通常，我们在讲解面向对象的时候喜欢把一个对象比作一个人（或物体、生物），以此解释对象的行为。

  在这里，我们不妨把调用栈当作一个对象。但是用一个人来指代这个对象似乎并不太容易理解，比如：

假如我们需要将一个会分叉的管道按连接顺序（ DFS ）一个不漏且不重复的遍历一遍（保证管道没有回路，并且可以从任意一点到达所有位置）。
那么我们解释的时候就会变成这样：

  1. 我从 α 点开始遍历管道，假如 α 点连接了 Nα 个管道
  2. 我让我以第一个相连的管道为起点继续遍历下面的管道
  3. 我让我以第二个相连的管道为起点继续遍历下面的管道
  4. 以此类推，直到遍历完所有相连的管道

  这么看似乎很模糊，我让我自己干新的活和我直接干这个新的活有什么区别吗？

  所以这里我们将调用栈当作一个由若干个人组成的群体会更加合理且容易解释，如图所示：

成员图

  下面，接着让我们以上面的遍历管道的例子看这个问题。

  当我们假设 A 为程序的入口，即我们要从某个点开始遍历管道的时候，会先告知 A 我们需要从 xxx 点开始遍历管道。

  现在，A 收到了我们的指示，它开始尝试遍历管道，但是这个工作对于一个人来说有些复杂，于是它选择将这个任务切分下来交给其它人合作完成。假设 α 点连接了 3 条管道，那么他就会将任务分为 3 份交给别人。如下图所示：

第一次任务分解

  B、F、G 三人分别接到了从 β、γ、λ 开始遍历管道的任务（同时会被要求不遍历已经遍历的点）。同理，三人也会将任务切分交给它人完成。

  现在我们假设 β、γ、λ 三个点就是管道的终点，那么它们发现没有新的点可以遍历后就会告诉 A 它们遍历的管道，然后 A 收到三个人的反馈后再告诉我们有哪些管道。

  完整代码和效果图如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 不给出建图的代码
// 类名后面的小括号是构造函数
/** 管道对象 */
class Pipe(
    /** 存储当前管道的编号 */
    val id: Int,
    /** 存储当前管道连接的管道 */
    val linked: List<Pipe>
) {
    
    // (Pipe) -> Unit 是指接受一个函数，这个函数以 Pipe 为参数，无返回值
    /**
     * 遍历管道
     * @param consumer 对正在遍历的管道自行操作
     */
    fun dfs(consumer: (Pipe) -> Unit) {
        val viewed = TreeSet<Int>()    // 用红黑树存储已经遍历的节点列表
        fun dfsHelper(consumer: (Pipe) -> Unit) {
            consumer(this)
            viewed.add(id)
            // forEach 遍历集合中的所有元素，it 为当前正在遍历的对象
            linked.forEach {
                // 检查节点是否访问过，如果被访问过就跳过该节点
                if (it.id !in viewed)
                    dfsHelper(consumer)
            }
        }
        dfsHelper(consumer)
    }
    
}

效果图

  最终会有类似这样的效果图，当然实际应用中可能并不会让所有人都分配到任务。

  那么调用栈溢出又是怎么一回事呢？上图中演示的是刚刚好每个人都被分配到任务的情况，那么如果这时候 T 还需要向下分配任务就会出现调用栈溢出。就是当一个人试图继续向下分配任务，但此时群体中已经没有空闲的人（所有人手头上都有任务），就会出现无法保存任务状态的问题，这就是我们平时说的调用栈溢出。

  当然实际应用中不会像上面的图中画的那么简单，因为实际上一个人是可以被重复分配任务的，当当前它处理的任务完成后它就可以恢复到空闲状态，等待接受下一个任务。

  到这里我们就介绍完了，还没有理解的小伙伴可以把不理解的内容发到评论区，我再进行补充。

创作不易，扫描下方打赏二维码支持一下吧ヾ(≧▽≦*)o