1回答

liuyubobobo

2019-03-07

已采纳

你的字写得好漂亮，有兴趣的话可以教教我怎么练字：）

另外，大赞你的学习方法。很多同学会忽视在程序编写，尤其是算法逻辑编写的过程中，纸笔的作用，只是盯着代码看。但其实，对于复杂的逻辑，使用纸笔整理逻辑是非常非常有意义的。

对于这个课程，对于递归调用，我确实讲得不够详细。在课程设计之初，没有设想那么仔细的讲递归。后来根据大家的反馈，我发现这其实是我课程设计的失误。对于这个课程设计，可以参考这个帖子：https://coding.imooc.com/learn/questiondetail/16248.html 我在我的后续课程《玩转数据结构》中，更加清楚的基于链表讲解了递归，如果有需要，可以参考。

递归本身，确实是在计算机领域门槛比较高的一个概念（或者算法模式）。确实不是用一个例子两个例子，就能让学习者彻底掌握的。即使是编程的老鸟，即使是算法领域的老鸟，也的时候也免不了在递归的具体逻辑上犯糊涂。所以，如果你第一次接触dfs，理解到现在的水平，已经非常了不起了。

你的图，对于dfs的整体理解上，我相信是正确的。但是，从我的角度，缺少一个很重要的过程。就是“回去”。

递归调用其实和普通的函数调用没有区别。对于普通的函数调用，A调用B，会中断A函数的逻辑，开始执行B函数的逻辑，一旦B函数的逻辑执行完成，会“回到”A函数中调用B的位置，继续执行A函数。

递归调用同理。只不过，A还是调用A而已。但是，由于调用过程传参不同，所以调用的第二个A，具体的运算会和A不同。

比如对于如下这个简单的含有四个节点的图，我会值的递归调用过程是这样的：）

0 - 3
|
1 - 2

简单文字描述如下：

从0开始调用dfs；

看到0的第一个相邻节点是1，调用dfs(1)；

来到节点1；

对于节点1，其实会先看到1有相邻接点0，但因为0已经来过了，忽略（visited的意义）；（这个过程我画的图中没有）

对于节点1，看他有第二个相邻节点2没有访问过，调用dfs(2)；

来到节点2；

对于节点2，他有相邻节点1，但已经访问过了，忽略；

除此之外外，节点2没有相邻节点了，此时，返回他的上层调用，也就是调用dfs(1)的函数中，继续看1还有没有相邻接点；

回到dfs（1）,1也没有其他相邻节点了（0和2都看过了），回到dfs(0)！

在dfs(0)中，0还有另一个相邻接点3！所以调用dfs(3)；

来到节点3，3有相邻接节点0，但是已经访问过了，没有其他相邻节点了，递归结束，又回到了dfs(0)

现在，0也没有任何没有访问过的相邻节点了，所以，整个递归函数的初始调用dfs(0)结束了。

整个递归过程结束：）

希望你通过这个过程，再仔细体会一下递归的执行过程。（但其实我觉得你的理解应该是正确的）。如果觉得有必要，使用单步跟踪的方式，一步一步基于一个简单的图，看一下整个递归调用过程是怎样。我个人认为这是非常有意义的一件事情：）

现在说你问的重点，递归结束条件。

通常，我们在写递归的过程中，会把递归拆分成两步：递归结束条件和递归过程。这个范式一点儿毛病都没有。但是，对于有一些递归过程，我们可以把递归终止条件，融入到递归过程中。这个dfs就是一个很好的例子。

再具体讲这个例子之前，我先举一个我们之前学习过的二分搜索树的例子，以前序遍历为例。我们在这个课程中写出的代码是这样的：

void preOrder(Node* node){    
    if( node != NULL ){    
        cout<<node->key<<endl;    
        preOrder(node->left);    
        preOrder(node->right);    
    }    
}

注意，其实这个写法，就没有显示的表示递归终止条件，而是把这个条件放在了if中，对于递归的基本情况，也走到了这个函数的最后。

从我的角度看，用标准的递归写法，应该这样写：

void preOrder(Node* node){    
    // 递归基本条件
    if( node == NULL ) 
        return;    
        
    // 递归过程
    cout<<node->key<<endl;    
    preOrder(node->left);    
    preOrder(node->right);        
}

dfs同理。dfs的递归终止条件是什么？就是当前所到达的点，其所有的相邻接点都已经被访问过了。

所以，你可以写一个类似这样结构的递归过程（伪码）：

void dfs(int v){    
    // 递归基本条件
    检查v的所有相邻接点是否都被访问过，如果都被访问过，return    
        
    // 递归过程
    检查v的所有相邻节点，对于没有访问过的相邻接点u，调用dfs(u)      
}

但是，你很快就会发现，这个递归基本条件，和递归过程，拥有者类似的逻辑，都要检查v的所有相邻接点。所以，我们完全可以把他们合在一起。因为，在递归过程中，检查了一遍所有相邻接点以后，发现都被访问过了，就不会或触发新的dfs(u)，整个函数return，和我们的递归基本条件是一样的：）

所以，思考递归结束条件是没有问题的。因为，所有的递归，一定有结束条件！只不过，这个结束条件的判断会不一样。有的情况很简单，就是和一个数字做一下比较，比如二分搜索树的例子，就是看一下当前的root是否为空而已；但有的时候，会比较复杂，要运行一段逻辑，甚至会包括循环，甚至判断终止条件会包括递归！但不管怎样，都是用一段逻辑，来判断终止条件是否成立。

这段逻辑一旦确定，你就可以把它写出来。然后再思考递归过程。有的时候，递归过程和递归终止条件的逻辑可以进行融合。但是，不要把这种“融合”看做“常态”，或者思考递归的重点。思考递归，是需要想清楚递归的终止条件的。这种“融合”，是想多了，见多了，对递归理解的越来越透彻以后，自然而然的一种逻辑编写方式。但是，至少在我的脑子中，是清楚的明白，这个递归不是一个无限递归，他是会终止的：）

递归确实很抽象，我不确定我的表述足够清晰。通过一两个例子就吃透递归，本身也是不现实的。我的建议是：大量的接触递归相关的问题。见多了，想多了，慢慢就越来越熟练，甚至会“不自觉地”，“自然而然地”写出正确的代码：）

做个小广告：我的《玩转算法面试》课程中，包含大量对递归问题的深入解析，有兴趣可以参考：）https://coding.imooc.com/class/82.html

加油！：）

4

2

liuyubobobo

回复

周泓印

谢谢老板支持！：）

2019-03-07

共2条回复