遞歸有什麼意義？

01-04

遞歸除了能讓代碼簡潔，既占內存又費時間，這樣的演算法有什麼意義么？

程序是用來抽象描述世界的。遞歸在現實世界無處不在，可能宇宙就是遞歸的。

在程序中使用遞歸，是為了更好更直觀的描述世界。

遞歸是計算機科學的重要方法

很多概念都是遞歸定義的

遞歸只是多壓一個棧指針進內存。並沒有費時間。

費時間說明你的演算法不好。

有些問題用遞歸解決更容易，尤其是那些本身就是用遞歸描述的問題。

遞歸是計算的基礎。

好像所有的回答都默認同意了遞歸比循緩慢，但這是不對的，好多語言（如 Scheme）循環只是遞歸的語法糖，並且保證可以用循環解決的問題，遞歸不會比循環慢。

建議 Google 如下關鍵字：尾遞歸優化。

當然，C 語言是不行的，但 gcc 在優化開到 O2 時也會進行的簡單的尾遞歸優化。

# 04-Nov-2014 Update

遞歸的本質是棧。

如果一個演算法不需要棧，那麼你用遞歸的時候，這種遞歸是可以優化的。只是現實是很少有語言會進行優化。

如果一個演算法需要棧，即使你不用遞歸，也要手工寫一個棧，不如遞歸方便。只是有些語言（如C）棧太小了，所以一不小心就爆了。

我覺得遞歸是演算法里很能體現把「未知不熟悉的問題轉化為已知熟悉問題」這一數學思想的

遞歸的性能並不差，且不論尾遞歸優化，那些沒法轉化為循環的情況，你真的認為棧幀指針的移動會比自己壓棧慢嗎？

遞歸的用處，與其說是讓代碼簡潔，我更覺得這只是遞歸的附帶好處而已（事實上是壞處，代碼簡潔，但反覆調用函數，對於效率來說反而是降低了）

遞歸最大的益處是，可以簡化問題。事實上，有些問題，不用遞歸的思想，幾乎是無法代數解決的

舉個例子，玩漢諾塔

漢諾塔_百度百科

ABC三個柱子，在A上按順序放置n個大小遞增的圓盤，如何藉助B柱，將原盤放到C柱，

要求：一次僅能移動一個原盤

移動中依然要求保持上小下大

當n=3，你可能能妙算

當n=4，應該你二年級可以做

上帝讓n=64,按照百度的解釋，你移動到身心俱焚都弄不完，更不要說你寫出演算法

然而，用遞歸的思想，做這件事，僅僅是計算量的問題，具體思想，可自行百度。

沒有遞歸，冥思苦想，往往也得不出一個有效地解決辦法。

總之，遞歸就是給傻人開的一扇窗，給聰明人留的一個巧。

遞歸的意義在於，讓人像人一樣去思考，讓計算機像計算機一樣去計算。

遞歸的意義就是，由於人腦的局限性而使機器低效率的運作。

遞歸是把複雜的問題歸一到一個子問題的一種解決方案。

/* 不恰當的例子 */

比如使用遞歸的線段樹就比非遞歸的分段Hash要爽的多。。。

/* 不信你去做Codeforces 445E */

多費一點機器內存，少費一點程序員的時間。看你認為哪個更寶貴了吧。

遞歸演算法本身並不更費時間呀，如果費時間可能是內存不夠，頻繁進行磁碟換入換出引起的，原因在於磁碟存取速度慢，可以考慮尾遞歸，佔用內存更少。

遞歸本身不是演算法。脫離問題討論某類寫法是「既占內存又廢時間「簡直胡扯。

因為遞歸好寫啊，寫一寫奇怪的結構的時候最棒了。

反正莫名喜歡遞歸，我現在寫過的東西幾乎都是遞歸，包括我的解釋器，我的爬蟲，我的 2048 AI 什麼的。

一個遞歸的問題,你不用遞歸的演算法那不是反人類嗎?

方便

LZ可以看一看"動態規劃"的內容

遞歸很多時候是一個問題最直覺、最方便的解法。想想快速排序。

但具體到 C 上來說，很多時候還是需要程序員手工實現為非遞歸的方法才能真正被用於解決有意義的數據量的問題。