1
xuwenhao 2014-07-17 00:44:05 +08:00 via iPhone
我见过所有的面试程序不能快速将递归转成循环的我总结下来都是写程序不熟练或者说不太会写程序的。另外,人月神话是说什么的你确信你看过?
|
3
jsonline 2014-07-17 00:49:29 +08:00 via Android
一般程序里面真的基本用不到递归,你确定递归更好维护?
|
4
vjnjc OP @jsonline 我不大確定,所以看看別人都是怎麼做的。因为在更早的时候有过一次糟糕的过早优化,使得我每次去维护它都要看半天,所以现在写代码都是按照最简单的结构写。
|
5
66CCFF 2014-07-17 01:19:57 +08:00 via Android
递归的话栈大小可能会成为一个坑?
|
6
imcotton 2014-07-17 01:22:44 +08:00 1
使用递归的正确场景:
- 性能无关的工作环境中 ✔ - 面试官考察且有异议时 ✖ Q: 你的代码就是写出来看的? A: “Write Programs for People First, Computers Second” Q: 有其他的解法么? A: 有 while {...} |
8
vjnjc OP @66CCFF 会成为坑的。关键是我经验不够,不知道多少数量级会成为坑,于是最简单的办法就是先让代码work,有性能问题就改
|
10
JustFuckingDoIt 2014-07-17 01:40:36 +08:00
《人月神话》有毒
|
11
akfish 2014-07-17 03:47:36 +08:00
递归并不见得就比循环更可读/更可维护,反之亦然。
最重要的是问题的语境,问的是算法题,算法侧重的是什么?效率和性能。End of story. 单独把一个算法拿出来叫你实现,就已经脱离了工程环境了,这种场合过于纠结可维护性等等问题,就跑题了。 其实算法题的目的就是让人家知道,如果有一天架构师决定某模块要用什么算法叫你写,你写得出来不。 |
12
lookhi 2014-07-17 06:31:03 +08:00 via Android 1
就递归来说
还有编译器最后会帮你一把 |
13
pepsin 2014-07-17 06:37:38 +08:00
很逗,现在高级点的语言都有编译器帮你在执行层面把尾递归转化为循环了。
|
14
abscon 2014-07-17 07:22:33 +08:00 via Android
@jsonline 要看要解决的问题,是否天生地包含了递归的概念。如果是的话,而且是那种无法转成尾递归的递归,那么避免显式递归就是矫情的。
因为此时递归一定会体现出来,要么是在函数层面,要么是你自己写一陀数据来模拟调用栈。显然前者更容易维护,有可能还更高效 |
15
huangyan9188 2014-07-17 08:43:05 +08:00
递归事实上在我们写程序中很少会用到的,递归本身有些不确定性。为什么说是不确定性,或者说是不稳定性,为什么说是这样,取决于算法的复杂程度。如果是一个复杂的算法,那么递归带来的机器损耗很难估计,因此算法性能的优化也很难进行,相反,如果是非递归算法的话,哪怕是while循环,仍然可以找到优化的办法。
因此,面试的时候,递归和非递归同时给出来,且说出两者各自的执行效率(时间复杂,空间复杂)应该才是最合适的。 但确实有一点就是,递归本身用到的不多。 |
16
shuax 2014-07-17 08:46:58 +08:00
看了楼上的评论,写erlang的哭了。
|
17
lengbing 2014-07-17 09:14:20 +08:00
看了楼上的评论,写lisp的哭了。
|
19
guoxx_ 2014-07-17 09:37:40 +08:00 via iPhone 1
从楼主的语境中来看,在这道问题的解决方案上,是递归更易于维护,while效率更高。
那这里有两个问题: 1. 程序能否被编译器实现为尾递归,消除调用栈。 2. 能否实现成迭代形式。 上面两种形式任一种都能够使用递归,又不影响效能。 另外我认为代码是可读,易维护为第一标准的。前提是写代码的人有足够的能力。 |
20
tiancaiamao 2014-07-17 09:45:23 +08:00
scheme表示不支持while,只有一种方式实现循环,那就是用递归
|
21
hyq 2014-07-17 10:44:53 +08:00
@huangyan9188 c++也支持尾递归,c++也哭了
|
22
pp3182429 2014-07-17 11:09:53 +08:00
以前感觉写递归很cool,后来面试了几次。发现基础打扎实了才是对的,其实基础扎实了,即使有的递归不能转换为循环,照样能自己用栈实现,将函数栈转换为数据栈,会好很多。看起来也不复杂。重在熟练吧。。
|
23
frankzeng 2014-07-17 13:22:52 +08:00
面试的时候经常有问到递归,但实际工作中又很少用到,这算不算是一个奇技淫巧。
|
24
multiple1902 2014-07-17 13:24:53 +08:00
写驱动确实用递归比较少。
|
25
nsa 2014-07-17 14:02:39 +08:00
看了楼上的评论,写汇编的瘫了
|
26
abscon 2014-07-17 14:27:02 +08:00 1
@pp3182429 我在前面的说法正好针对你的这种情况:“照样能自己用栈实现,将函数栈转换为数据栈,会好很多”。请给出证明为什么**要好很多**?
找照这种逻辑来说的话: 1. c语言就不应该支持函数的递归调用,反正程序员能用数据栈手工模拟函数栈 2. c++就不应该支持面向对象编程,反正C程序员能手工模拟面向对象 3. 各种支持namespace的语言是吃饱了撑的,反正程序员能用命名规范来模拟名字空间 4. c语言就不该支持else,while,for这几个关键字,反正程序员能用if和goto来模拟 我的主张是,不要刻意的去用递归,也不要刻意的不去用递归 应该是仔细分析要解决的问题,写完代码后一看,恩,原来是个递归(或者,恩,原来没有用到递归)。 |
27
loryyang 2014-07-17 14:48:21 +08:00
递归这个东西一般不太用,因为现实环境,搞不好会爆栈。。如果用个while能够搞定,我一般不会去用递归。。。
|
28
pp3182429 2014-07-17 14:56:50 +08:00
@abscon ==#我只是觉得,本来栈里要放函数及各种形参临时变量,现在只要放要操作的数据或者只需要每一层栈记录一个状态了,这样省地方。。
对于下面这么多问题,无非是哪个适合用哪个么。哪个适合自己用哪个,有什么可争的么?每个人选择不一样而已。 |
29
abscon 2014-07-17 15:52:04 +08:00
@pp3182429 “数据栈”这种东西在堆里分配,效率比函数栈可是要差的。
要是按照楼主的面试官的喜好,为了效率高而舍弃递归,那么反而会选出一个效率差的方案(和他的直觉相反了,哈哈)。 你只用数据栈,不可避免的要比那些“各种形参临时变量”多写一些代码。要定义struct/class吧?要分配内存吧?如果没有垃圾收集还要销毁内存吧?不管是代码还是实际占用内存,都不会“省地方”的。 只用数据栈有几个用处: 1. 显示水平高,咱不需要用递归的语法也能完成哦! 2. 避免堆栈溢出。 3. 可以用于不支持递归语法的语言。 在我看来,只有2和3才是有意义的做法。 你说的“个人选择不同”,我很赞同,我只补充一点,任何时候,如果程序员在“使用语言直接支持的语法”和“用其他方法模拟”中选择了后者,那这个选择极有可能是错误的。 |
30
tabris17 2014-07-17 16:38:41 +08:00
看应用场景了,如果递归深度是可以预见的,那用递归也无妨
|
31
tabris17 2014-07-17 16:41:38 +08:00
递归并非是人力和效率的问题,而是代码可靠性的问题,用递归就需要考虑栈内存耗尽的问题,call和ret的性能损耗倒是其次。
题外话,编译器优化的时候不会能把某些形式的inline函数的递归自动转为循环的么 |
32
lightening 2014-07-17 20:40:39 +08:00
代码写出来,当然要首先适宜人类阅读,其次才是执行能高效了。不然为什么我们不都用汇编?
|
33
vjnjc OP 不要究诘于递归了,我只是举了一个看上去很不恰当的例子。。。。
我就是想听听别人对于 代码维护性vs代码性能 的看法~ |
34
vjnjc OP @JustFuckingDoIt 我感觉真的很有用啊。不知道做产品的怎么样,我是做项目的,有一个Java文件光是import语句 都有100行,我感觉很复杂,特别像《人月神话》描述的焦油坑,一不小心就会陷进回归测试出BUG的大沼泽。
|
36
vjnjc OP @huangyan9188 递归与循环复杂度一样的吧。因为代码里面用到的循环和变量才记入复杂度,而函数调用的额外耗费不计复杂度(个人看法,欢迎指正)
|
38
AlanZhang 2014-07-17 21:50:10 +08:00 via iPhone
维护第一,性能第二。现在人比机器贵的多。
|
40
vjnjc OP @tabris17 Hello,你提到‘call和ret的性能损耗倒是其次。’ 以我的知识只知道‘递归会同时多消耗栈和cpu跳转时间’,请问你的结论是怎么得出的?是工作经验还是某方面的书籍?
|
41
ffffwh 2014-07-17 22:01:41 +08:00
|
44
huangyan9188 2014-07-18 00:26:53 +08:00
@vjnjc 空间复杂度差别很大
在做算法优化方面 递归显得很糟糕 |
45
iwege 2014-07-18 10:25:52 +08:00
递归很好维护么?是相对什么来说的?.....
|
48
williamx 2014-07-18 13:50:53 +08:00
涉及到“递归”就不仅仅是性能或是可维护性的问题了。这个问题的解是:只在没有其他办法的时候才用递归!
|