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

我觉得递归代码更简洁，readable。我以前也是觉得iteration更好，但是时间长了自己都看不懂。如果recursion，就很简洁啊。而且有很多median或者hard的题都是其中某一步用递归啊，所以到处都是递归，只不过没有发现递归的眼睛吧。加油！

真相是几乎所有迭代都能用递归的方法去写。

请假设某个题的算法是A，那么你写的程序实现P就是对A的“编码”。多种“编码”都可以表示同一种东西，比如阿拉伯数字5和罗马数字V都表示「5」这个概念。递归的写法，就是对“你脑中的算法”的一种“相对于迭代写法更容易背人理解的编码”。

那么问题来了，既然它容易理解，为什么很多时候递归不那么“流行”？这里有一些历史因素，一个很不幸的事实就是，主流语言如Java C等没能正确实现尾调用，而正确的尾调用是递归函数编译后能够不堆栈溢出的关键。（实际上所有的非尾递归都能用一种通用的方法转变为尾递归，叫CPS变换）

只要编译器正确实现了针尾调用，那么递归的写法就可以既保留人易理解，又好构思的特性，又能够在编译后产生和迭代一模一样的机器码。

某种程度上讲，当代程序员需要思考的很多内容并非“算法”层面的，而且为了讨好编译器的做法。编译器凝结了先辈的最，需要很久之后的未来才能慢慢消除。



补充内容 (2020-1-15 13:19):
先辈的最>先辈的罪

而且>而是

手机9键打的，错别字有点多

补充内容 (2020-1-15 13:26):
此处不适合多讲细节了，有兴趣我空下来的在论坛专门写个关于recursion在算法题里怎么用以及什么情况下推荐用，什么情况下不推荐用之类的专题贴