灵魂发问：递归在面试考察中到底什么水平？？

大佬们好，小妹又来问问题了
是这样，我按照Lc上的topics tag统计了以下，发现recursion才35道啊？！？！占比千分之30？而且结合出题的related topic也很有限
大约是这个水平：

而且，听说 能用recursion解的题型，都能用迭代写法解决，并且更不容易出错，更容易解释（讲）清楚
那么问题来了：
1.面试，面经上，无论是店面还是OA还是onsite， 对recursion的考察是个什么情况？什么水平？真的会考到吗？
2.为啥（如果真的是不重要）lc占比这么小，约等于不太重要，各种算法班还要花大力气讲呢？不是面试为主吗？又不是学科授课为主

望大佬解答
提前感谢

我觉得dfs其实很能考察抽象思维跟逻辑思维能力。。其实所有的dp题都能用dfs的解决（只是效率不高），注意，是所有。
很多题，一眼看不出dp的状态转移方程，都可以先用dfs弄出一个暴力解法，在oj上小规模的test case是能过的（大数据case的会TLE/MLE for sure）
在实际面试的时候这也可以作为一个可行解（至少能weak hire/hire）了
写裸奔dfs之后，看看能不能剪枝+记忆化来优化，这一步弄完，从渐进意义上就已经跟dp解答（如果有）复杂度一样了（但是实际可能会慢，因为递归要各种压栈出栈）
可行解 + 优化 = strong hire ！✌️

可以说非常常见, 递归是一种程序实现方式并不是算法, 凡是函数调用自己的都称为递归.

算法考试里非常常见的dfs基本上要用递归实现.

理论上递归的程序也能用非递归做, 但是仅限于贼简单的case, 复杂的题你写非递归就算写出来也没人能看懂.


你搜一下dfs有多少题就知道了

肯定会考的，递归都搞不清楚的程序员谁敢招

Enalynn 发表于 2019-10-12 06:10
可以说非常常见, 递归是一种程序实现方式并不是算法, 凡是函数调用自己的都称为递归.

算法考试里非常常 ...

lc上DFS的题目是很多，大概是第5多，有100多道
可是lc上DFS 相关tag也没有标明用到recursion 啊？
这是个什么情况...

akdhfikbk 发表于 2019/10/12 06:15:51
lc上DFS的题目是很多，大概是第5多，有100多道
可是lc上DFS 相关tag也没有标明用到recursion 啊？
这是个什么情况...

一道题本来就有很多种分类，有的不止一种解法的题目分类就更多了。比如有的题dp能做dps也能做。
lc没有也不可能也不需要把tag标的很完备，仅供参考。
你就知道recursion你不得不会不会不行一定要会就好了
而且如楼上所说，dfs这个算法很多时候用recursion来实现，但往往tag只有dfs。

akdhfikbk 发表于 2019-10-12 06:15
lc上DFS的题目是很多，大概是第5多，有100多道
可是lc上DFS 相关tag也没有标明用到recursion 啊？
这是 ...

他label法有问题. lc的label也是人添加的, 一道用递归的dfs可能大家会label成dfs不会label成递归

因为dfs是算法, recursion不是算法, 是程序实现方式.

dfs和递归不是一个维度上的东西. 建议分类的时候还是按算法, tree的label也很多, 但是你要是刷tree, 有树上dfs, 树上bfs, 树上dp等等, 他们并不是一个类型的题.

递归是一种程序的实现方式，并不是一种具体的算法。

就像楼上的盆友们说的， 涉及到DFS的基本都是用递归来实现，因为你不递归就只能人造一个栈来维护，得不偿失。

当然不止dfs里有递归， 比如经典的排序 mergeSort quickSort，同样是递归的运用。

会考到，树的题目用recursion做

dfs主要实现方式就是递归和stack，很多人都会选择用递归实现，写着简单些

类似于array每个题都要用到，但是array的tag只有几十题。。