有什麼只能通過遞歸來實現嗎？

我不確定，但我聽說過只能通過遞歸實現的算法。有人知道這樣的事情嗎？有什麼只能通過遞歸來實現嗎？

2010-08-10 Shubham

看看http://stackoverflow.com/questions/1011448/necessary-uses-of-recursion-in-imperative-languages – 2010-08-10 17:03:25

你應該看看下面的問題：http://stackoverflow.com/questions/3451439/is-there-anything-which-can-only-be-by-recursion – 2010-08-10 17:19:29

在命令式語言中？ – 2010-08-10 17:22:35

您需要澄清您正在討論的遞歸類型。有算法遞歸，並且在實現有遞歸。確實，任何遞歸的算法都允許簡單的非遞歸實現 - 人們可以通過使用手動堆棧模擬遞歸的標準技巧來輕鬆實現。

但是，您的問題僅提供算法。如果我們假定它具體是關於算法遞歸，那麼答案是是，這裏有一些固有的和不可避免的遞歸算法。在一般情況下，不可能用非遞歸算法替換固有遞歸算法。構建固有遞歸算法的最簡單方法是首先採用固有遞歸的數據結構。例如，假設我們需要遍歷一棵只有父 - 子鏈接的樹（並且沒有子 - 父鏈接）。想出一個合理的非遞歸算法來解決這個問題是不可能的。

所以，這就是你的一個例子：只有父 - 子鏈接的樹的遍歷不能由非遞歸算法執行。

固有遞歸算法的另一個例子是衆所周知的QuickSort算法。 QuickSort始終是遞歸的，並且它不能簡單地轉化爲非遞歸算法，因爲如果您成功完成此操作，它將不再是QuickSort。這將是一個完全不同的算法。當然，這聽起來像純粹的語義練習，但是這也是值得一提的。

來源

2010-08-10 17:17:11 AnT

你能解釋一下「算法遞歸」是什麼意思嗎？我從來沒有聽說過。關於你的快速評論：你是說「常用」（恆定空間）實現不是快速排序，還是算法遞歸，即使它不是實際遞歸？ – sepp2k 2010-08-11 08:55:58

*算法遞歸*（或*遞歸算法*）我的意思是基於以下原理構建的算法：1）使用分而治之（D＆C）方法，即通過將問題分解爲更小的子區域來解決問題， 2）D＆C方法產生的子問題以LIFO順序解決，即子問題等待輪到他們解決在堆棧狀結構中。如果無法通過常數限制該LIFO數據結構的大小，那麼該算法本質上是真正的*遞歸*。 – AnT 2010-08-11 16:28:55

此外，我不知道這樣的東西作爲恆定空間QuickSort。 QuickSort的智能實現需要'O（log n）'空間。如果我們引入平臺限制（比如給定平臺上最大數組的大小），我們當然可以用相對較小的常量來限制空間，但這與算法本身沒什麼關係。 QuickSort仍然（並始終）遞歸。另外還有深度優先搜索。 – AnT 2010-08-11 16:31:26

如果我正確地記住了我的算法，那麼遞歸無法通過堆棧和循環完成任何操作。然而，我手邊沒有這方面的正式證據。

編輯：它發生在我身上，答案可能是唯一可以通過遞歸實現的，不能用堆棧+循環實現的，是堆棧溢出？

來源

2010-08-10 17:01:07 Mark

當然，你可以產生一個沒有遞歸的stackoverflow：創建一個有限容量的堆棧數據結構。現在繼續推動該堆棧直到超過容量。堆棧溢出。畢竟，當你有無限遞歸時，會發生什麼（除了容量超出的棧是進程的調用棧而不是你在程序中明確創建的棧）。 – sepp2k 2010-08-10 17:06:10

這是一個笑話，我很抱歉，如果它不好笑。 – Mark 2010-08-10 17:09:13

不，sepp2k似乎已經設置了'senseOfHumor = false;' – AllenG 2010-08-10 17:12:31

您始終可以通過保留自己的堆棧來模擬遞歸。所以不行。

來源

2010-08-10 17:01:08 sepp2k

任何遞歸函數也可以轉換爲等價的迭代函數。 – quantumSoup 2010-08-11 01:26:01

下比較遞歸與非遞歸實現：http://www.sparknotes.com/cs/recursion/whatisrecursion/section1.html

摘錄：

鑑於遞歸總體效率較低，我們爲什麼要使用它？有兩種情況下遞歸是最好的解決辦法：

的問題是使用遞歸更清楚解決：有很多問題，其中遞歸解決方案更清晰，更清潔和更易懂。只要效率不是主要問題，或者各種解決方案的效率是可比較的，那麼您應該使用遞歸解決方案。
通過遞歸解決一些問題更容易：有一些問題沒有簡單的迭代解決方案。在這裏你應該使用遞歸。河內問題塔是一個迭代解決方案非常困難的例子。我們會在本指南後面的章節中看看河內的塔樓。

來源

2010-08-10 17:06:36

你只是在尋找一個遞歸的實例嗎？最近我的朋友和我實現了Haar Wavelet函數（作爲開始學習Ruby的練習），這似乎需要遞歸。除非任何人沒有遞歸實現它？

我會想象任何時候一個人不知道堆棧的深度正在迭代，遞歸是合乎邏輯的路徑。當然，它可能適用於一些被破解的循環，但那是好代碼嗎？

來源

2010-08-10 17:07:37 David

有什麼只能通過遞歸來實現嗎？

回答

相關問題