关于程序员的产出效率以及代码的执行性能（思考题）

[vjnjc]

我的问题是：程序员的开发、维护效率重要还是代码的执行性能重要？

不知道类似的想法有没有在v2ex上提及，事情的缘由是昨天我去SAP面试，和面试官观念冲突。

面试官：（这道算法题）为什么要用递归？
我：（我当然知道递归调用会消耗调用函数的栈，）我希望（别人）阅读、维护这段代码能够更轻松一点。
面试官：你的代码就是写出来看的？
我：。。。（别人看不懂怎么维护啊）
面试官：有其他的解法么？
我：有的，用个while套起来。

十分种后，我的比较优美的代码变成了我都不想承认的代码。
PS:括号里的是我结合语境杜撰出来的，当时对话并没有这些部分。

我的看法：由于鄙人是《人月神话》的忠实粉丝，所以当然是人力比较重要！！写出一段阅读性好，可维护的代码是程序员的职责，而写出奇葩、差劲的代码都是被（进度或者是性能要求）胁迫的。

不吐不快啊，欢迎各位exer表达自己的看法。
由于我能力有限，如有不对之处也欢迎板砖。

[xuwenhao]

我见过所有的面试程序不能快速将递归转成循环的我总结下来都是写程序不熟练或者说不太会写程序的。另外，人月神话是说什么的你确信你看过？

[vjnjc]

@xuwenhao 看过的，至今留有印象的是两部分，大型项目的焦油坑和外科手术的主刀医师,其他忘光了

[jsonline]

一般程序里面真的基本用不到递归，你确定递归更好维护？

[vjnjc]

@jsonline 我不大確定，所以看看別人都是怎麼做的。因为在更早的时候有过一次糟糕的过早优化，使得我每次去维护它都要看半天，所以现在写代码都是按照最简单的结构写。

[66CCFF]

递归的话栈大小可能会成为一个坑？

[imcotton]

使用递归的正确场景：

- 性能无关的工作环境中 ✔
- 面试官考察且有异议时 ✖


Q: 你的代码就是写出来看的？
A: “Write Programs for People First, Computers Second”


Q: 有其他的解法么？
A: 有 while {...}

[vjnjc]

@imcotton ...这位兄台太专业了，顶

[vjnjc]

@66CCFF 会成为坑的。关键是我经验不够，不知道多少数量级会成为坑，于是最简单的办法就是先让代码work，有性能问题就改

[vjnjc]

@imcotton 话说你的✔和✖是怎么来的？用了某一种输入法打的？

[JustFuckingDoIt]

《人月神话》有毒

[akfish]

递归并不见得就比循环更可读/更可维护，反之亦然。

最重要的是问题的语境，问的是算法题，算法侧重的是什么？效率和性能。End of story.

单独把一个算法拿出来叫你实现，就已经脱离了工程环境了，这种场合过于纠结可维护性等等问题，就跑题了。

其实算法题的目的就是让人家知道，如果有一天架构师决定某模块要用什么算法叫你写，你写得出来不。

[lookhi]

就递归来说
还有编译器最后会帮你一把

[pepsin]

很逗，现在高级点的语言都有编译器帮你在执行层面把尾递归转化为循环了。

[abscon]

@jsonline 要看要解决的问题，是否天生地包含了递归的概念。如果是的话，而且是那种无法转成尾递归的递归，那么避免显式递归就是矫情的。

因为此时递归一定会体现出来，要么是在函数层面，要么是你自己写一陀数据来模拟调用栈。显然前者更容易维护，有可能还更高效

[huangyan9188]

递归事实上在我们写程序中很少会用到的，递归本身有些不确定性。为什么说是不确定性，或者说是不稳定性，为什么说是这样，取决于算法的复杂程度。如果是一个复杂的算法，那么递归带来的机器损耗很难估计，因此算法性能的优化也很难进行，相反，如果是非递归算法的话，哪怕是while循环，仍然可以找到优化的办法。
因此，面试的时候，递归和非递归同时给出来，且说出两者各自的执行效率（时间复杂，空间复杂）应该才是最合适的。
但确实有一点就是，递归本身用到的不多。

[shuax]

看了楼上的评论，写erlang的哭了。

[lengbing]

看了楼上的评论，写lisp的哭了。

[scorpius]

@shuax +1

[guoxx_]

从楼主的语境中来看，在这道问题的解决方案上，是递归更易于维护，while效率更高。
那这里有两个问题：
1. 程序能否被编译器实现为尾递归，消除调用栈。
2. 能否实现成迭代形式。

上面两种形式任一种都能够使用递归，又不影响效能。
另外我认为代码是可读，易维护为第一标准的。前提是写代码的人有足够的能力。

[tiancaiamao]

scheme表示不支持while，只有一种方式实现循环，那就是用递归

[hyq]

@huangyan9188 c++也支持尾递归，c++也哭了

[pp3182429]

以前感觉写递归很cool，后来面试了几次。发现基础打扎实了才是对的，其实基础扎实了，即使有的递归不能转换为循环，照样能自己用栈实现，将函数栈转换为数据栈，会好很多。看起来也不复杂。重在熟练吧。。

[frankzeng]

面试的时候经常有问到递归，但实际工作中又很少用到，这算不算是一个奇技淫巧。

[multiple1902]

写驱动确实用递归比较少。

[nsa]

看了楼上的评论，写汇编的瘫了

[abscon]

@pp3182429 我在前面的说法正好针对你的这种情况：“照样能自己用栈实现，将函数栈转换为数据栈，会好很多”。请给出证明为什么**要好很多**？

找照这种逻辑来说的话：
1. c语言就不应该支持函数的递归调用，反正程序员能用数据栈手工模拟函数栈
2. c++就不应该支持面向对象编程，反正C程序员能手工模拟面向对象
3. 各种支持namespace的语言是吃饱了撑的，反正程序员能用命名规范来模拟名字空间
4. c语言就不该支持else,while,for这几个关键字，反正程序员能用if和goto来模拟

我的主张是，不要刻意的去用递归，也不要刻意的不去用递归

应该是仔细分析要解决的问题，写完代码后一看，恩，原来是个递归（或者，恩，原来没有用到递归）。

[loryyang]

递归这个东西一般不太用，因为现实环境，搞不好会爆栈。。如果用个while能够搞定，我一般不会去用递归。。。

[pp3182429]

@abscon ==#我只是觉得，本来栈里要放函数及各种形参临时变量，现在只要放要操作的数据或者只需要每一层栈记录一个状态了，这样省地方。。

对于下面这么多问题，无非是哪个适合用哪个么。哪个适合自己用哪个，有什么可争的么？每个人选择不一样而已。

[abscon]

@pp3182429 “数据栈”这种东西在堆里分配，效率比函数栈可是要差的。
要是按照楼主的面试官的喜好，为了效率高而舍弃递归，那么反而会选出一个效率差的方案（和他的直觉相反了，哈哈）。

你只用数据栈，不可避免的要比那些“各种形参临时变量”多写一些代码。要定义struct/class吧？要分配内存吧？如果没有垃圾收集还要销毁内存吧？不管是代码还是实际占用内存，都不会“省地方”的。

只用数据栈有几个用处：
1. 显示水平高，咱不需要用递归的语法也能完成哦！
2. 避免堆栈溢出。
3. 可以用于不支持递归语法的语言。

在我看来，只有2和3才是有意义的做法。

你说的“个人选择不同”，我很赞同，我只补充一点，任何时候，如果程序员在“使用语言直接支持的语法”和“用其他方法模拟”中选择了后者，那这个选择极有可能是错误的。

[tabris17]

看应用场景了，如果递归深度是可以预见的，那用递归也无妨

[tabris17]

递归并非是人力和效率的问题，而是代码可靠性的问题，用递归就需要考虑栈内存耗尽的问题，call和ret的性能损耗倒是其次。

题外话，编译器优化的时候不会能把某些形式的inline函数的递归自动转为循环的么

[lightening]

代码写出来，当然要首先适宜人类阅读，其次才是执行能高效了。不然为什么我们不都用汇编？

[vjnjc]

不要究诘于递归了，我只是举了一个看上去很不恰当的例子。。。。
我就是想听听别人对于 代码维护性vs代码性能 的看法~

[vjnjc]

@JustFuckingDoIt 我感觉真的很有用啊。不知道做产品的怎么样，我是做项目的，有一个Java文件光是import语句 都有100行，我感觉很复杂，特别像《人月神话》描述的焦油坑，一不小心就会陷进回归测试出BUG的大沼泽。

[vjnjc]

@frankzeng 我猜测是因为业务上面的算法会比较少，写业务很多都是增删改查，这种递归不起来。

[vjnjc]

@huangyan9188 递归与循环复杂度一样的吧。因为代码里面用到的循环和变量才记入复杂度，而函数调用的额外耗费不计复杂度（个人看法，欢迎指正）

[vjnjc]

@akfish 说得挺对，现在想起来究诘于面试的时候跟面试官争论是最无意义的。

[AlanZhang]

维护第一，性能第二。现在人比机器贵的多。

[vjnjc]

@abscon 多谢提醒，第一次听到尾递归优化为循环的细节，很开眼界。有没有推荐的书啊，关于编程的，任何方向的

[vjnjc]

@tabris17 Hello,你提到‘call和ret的性能损耗倒是其次。’ 以我的知识只知道‘递归会同时多消耗栈和cpu跳转时间’,请问你的结论是怎么得出的？是工作经验还是某方面的书籍？

[ffffwh]

@vjnjc
不只是尾递归，只要是尾调用（tail call），就能不压栈调用。
话说有个叫Continuation Passing Style (CPS)的东西挺好玩的，不知道的可以了解下。

[vjnjc]

@AlanZhang 同意。我不大确认是不是都是这么想的，所以想看看倾向于性能的程序员是基于什么理由

[vjnjc]

@ffffwh 多谢开眼

[huangyan9188]

@vjnjc 空间复杂度差别很大
在做算法优化方面 递归显得很糟糕

[iwege]

递归很好维护么？是相对什么来说的？.....

[xuwenhao]

@vjnjc 你为什么有一个假设是 性能 和 可维护性 是矛盾的呢？

[tabris17]

@vjnjc 我的意思是递归造成的性能损耗是其次的需要关心的，而不是说这个性能损耗是可以忽略的

[williamx]

涉及到“递归”就不仅仅是性能或是可维护性的问题了。这个问题的解是：只在没有其他办法的时候才用递归！