※ 引述《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) 但是它们的骨子里其实都还是一样的递回结构 换句话说, 有的时候虽然程式的表面上没有递回 但是实际上它的内涵正是递回的概念 并不是只有明写着的递回才是递回... --- 最近正好跟朋友闲聊聊到这个 那时聊的是为什麽有些程式初学者会在递回卡一阵子关 聊到後来我对这个问题的看法总结起来是这样的: 递回这东西其实就是数学归纳法 所以只要数学归纳法搞得懂就搞得懂递回 而之所以程式初学者会卡关的原因是因为为了计算结果追到枝微末节去了 而没有看到其实大架构只不过是数学归纳法而已 所以他们得要花跟当初理解数学归纳法一样的时间去理解递回 嘛, 这只是我的观察就是了 XD -- LPH [acronym] = Let Program Heal us -- New Uncyclopedian Dictionary, Minmei Publishing Co. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.41.35.96