※ 引述《liu2007 (薯)》之铭言：
: /递回 /recursive 都没看到相关的文章
: 想请问递回在 C or java 这些非人工智能的语言上的使用时机
: 使用递回写程式真的是很美妙，可是速度实在是很糟糕
: 而且一不小心内存就爆了
: 但是既然语言支持了递回，总是有个理由说能够在某些时候使用吧?
: 而这些时机到底是什么呢?
: google的几个结果大同小异：“通常问题很复杂，而且你不在意花费时间的时候”
: 所以递回只能活在假设情况下吗??
: 又或者递回只能活在使用的时候整个tree不会span很大的时候使用??
其实递回这东西是从数学定义来的
数学的定义方法里有一种叫做递归定义
https://zh.wikipedia.org/wiki/%E9%80%92%E5%BD%92%E5%AE%9A%E4%B9%89
而递回的程式其实就只是把这种概念直接程式化而已
也就是说, 当你的程式要计算的东西在数学上有着这种结构的时候
程式就可以很容易地使用递回去撰写
之所以实作上不常使用的原因－－速度慢－－并不是递回这个结构的错
而是因为当这个结构牵扯到一个以上的子问题时
子问题的计算次数会以指数成长的关系
(看看费氏数列就知道了;
如果每个问题只需要一个子问题的话 (像是阶乘)
那么递回写法其实不一定会慢那么多)
至于递回呼叫的空间问题 这也不是递回的错
而是因为初值太深 计算时为了要保持中间结果不得不使用一些空间
这些空间由于要记录除了我们计算的东西之外的资讯造成某种程度的浪费
为了解决这个指数成长的计数次数以及空间的浪费
我们有了笔记法 (memoization) 以及动态规划 (dynamic programming)
但是它们的骨子里其实都还是一样的递回结构
换句话说, 有的时候虽然程式的表面上没有递回
但是实际上它的内涵正是递回的概念
并不是只有明写着的递回才是递回...