1樓：大魔頭-諾鐵
2樓：pansz
遞迴的成本在於具體語言的實現，因為遞迴常常要儲存呼叫者的上下文。在遞迴層級較深時，這個儲存的開銷可能很高。
另外遞迴通常使用函式實現，而函式呼叫通常在傳統中被認為是比較高的開銷，雖然現在很多語言的函式呼叫並不比其他邏輯的開銷更高。
支援尾遞迴，tail call 之類的語言實現，遞迴與非遞迴成本基本相同。
例如 lua 就支援 tail call，放心的使用尾遞迴不增加任何開銷。
尾遞迴節省成本的原因是，他不需要將當前函式的上下文儲存在棧中，而是直接切換到新函式的上下文，或者先退出當前函式的上下文再啟動新的。
3樓：Cascade
對於計算機來說成本主要是大量的函式呼叫產生的額外記憶體消耗和處理器占用。
但其實一般用遞迴跑的小演算法，函式呼叫的開銷並不會大到顯著影響效率的地步。再加上編譯器的優化，效率並不會很差。
其實用遞迴的時候，成本主要花在想怎麼想演算法上面了。
4樓：
成本一般分兩塊：memory & running time就自己認知而言，不見得recursion的成本就很高吧，當然其對memory的要求相比於用其他的algorithm比來說只高不低。
拿sorting的兩種方法拿來比較insertion sortO(n^2)
merge sort
O(nlogn)
寫尾遞迴函式有什麼規律或技巧嗎？
海納 在設計的時候，可以先寫出迴圈版本，再把迴圈中所用到的區域性變數都變成遞迴函式的引數。這是實際開發中常用的一種辦法。可以參考我這篇文章 知乎專欄 例如，我們寫乙個函式，計算m的n次方，使用迴圈，就寫成這樣 public static double power1 double m,int n 把這...
數理邏輯裡的遞迴函式是什麼？
你需要學習遞迴論。最最簡單和入門的一本書 https 有老版中文版。 維洛逐風 如果乙個函式是由三個基本函式 零函式，後繼函式，對映函式 通過三種操作 替換，原始遞迴，極小化 獲得的，稱該函式是遞迴的 Htedsv 邏輯 邏輯 作為程式語言的抽象，可以看成乙個平面而沒有層次的 描述 對於可計算理論的...
程式設計的函式和數學的函式為什麼都叫函式？
哲學嘉 本質是一樣的，電腦程式的函式概念基於數學上的函式，只不過加了一些操作在裡面，所以變得跟數學上的函式有點不一樣 計算機中的函式包含輸入 輸出 資料處理還有操作 比如輸出到螢幕 而數學上的函式只關注數。在數學上，輸入 資料處理 輸出，這三者缺少任何乙個都是沒有意義的，而在電腦程式裡，就算你輸入 ...