现如今，递归的效率到底有多差

[snailsir]

时常会遇到一些人在我说出递归时反驳说，递归的效率很差。好像还记得大学学 C 语言时，谭浩强也这么写过，老师也这样教我们。

但，我在接触 lisp 之后，却发现处处都有递归的思想及应用，也没发现有什么差的地方，反倒是处理问题简单许多。

所以始终不明白递归的效率到底有多差。一点猜测是，那个时候，计算机很奢侈；但现如今，随便一台电脑，性能都很好啊。

[ruandao]

你那个是迭代,只是用递归的形式显示

[snailsir]

@ruandao ？

[ch3n2k]

尾递归可以用，在支持尾递归优化的语言里面

[monsoon]

有种递归叫尾递归。

[mthli]

是的，有种递归叫尾递归。

[caixiexin]

不是效率差，而是递归会导致内存溢出，尾递归除外- -

[ruandao]

@snailsir

恩, 应该是指这个:

https://gist.github.com/ruandao/b5897ffffd3bf9757f02

[YuJianrong]

1. 递归性能是真的差， call 一个函数的时候大多数语言都需要有一定程度的资源分配、释放等操作，这当然要比单纯循环性能更差。
2. 为了能回溯，递归函数的参数和地址需要分配在 call stack 上，大部分语言的 call stack 大小都是有限的，递归太深就会爆掉
3. 没有 side effect 的语言(如 lisp, haskell )当递归在尾部的时候可以做尾递归优化，这时函数其实并没有递归而被优化成循环了（实际上 lisp 没有循环本来做循环就得靠尾递归）。

顺便黑一下 lisp ，这玩意玩玩就好其实根本不能适应现代大规模开发，我看还是学好 C++/java/JS 比较实在。

[ryd994]

处理问题简单和性能好有什么关系？
有尾递归优化时，开销相对较小，但也无非就是循环而已，考虑到初始化之类的成本，还是不如循环。
没尾递归你就等着深度大的时候爆栈吧
其实递归就是利用函数调用的机制做循环而已

[pynix]

优化。。。。

[snailsir]

看到大家的回答，总结一下问题所在吧：

1. 说开销，感觉还是在 函数调用堆栈 上面，这个各语言是的限制又不一样。
2. 尾递归的话，得需要语言的支持。

但感觉以上两点，也并没有限制 递归的扩张啊。就像当年的 goto 语句一样（ linux 内核源码风格中提到了在什么情况下比较适合使用 goto ）

@ruandao 的例子然我想起了 lisp 里的做法貌似大都这样的，试了一下 php 版本的，居然也可以。



@ryd994
@YuJianrong

[ryd994]

@snailsir 限制再不一样，优化的再好，还是有，而且不会小。递归真心只有设计算法的时候感觉好。实现的时候就是大坑。出错的时候 debug 也更麻烦。 lisp 本来就是理论性很强的语言，感觉好不奇怪。 C 里面爆栈太容易。你确定递归用的很多？确实有递归好用的情况，但大多数情况都不是这样。