推 xcycl:structural induction ... 88.107.45.33 10/22 09:33
推 liu2007:感謝回文指教 106.1.108.108 11/02 11:49
※ 引述《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