2012-04-03 66 views
3

我在這裏是新手,我有一個問題困擾着我。我是初學者,所以請不要嘲笑我。 我想對大量元素進行遞歸快速排序,比方說100000.我知道這會導致堆棧溢出。我過去幾天一直在搜索Google,試圖找到一種方法來管理調用堆棧。不能真正找到一個好的信息來源。 我的理念是刪除每個遞歸調用的返回地址,除了最後一個,它將返回到第一個函數調用。我不知道這是否可能,或者如果它是這個問題的另一個解決方案。C - 用遞歸方法管理調用堆棧

P.S. :我想保持quicksort遞歸。

對不起,如果我的問題看起來很愚蠢,但我可以appreaciate任何相關的答案。 對不起,我的英語不好。 謝謝!

+1

發表一些代碼。如果遞歸可以被尾調用,你可能可以使其工作。 – 2012-04-03 23:40:02

+1

有兩件事會幫助;選擇數據透視表時不要使用簡單的方法,並且總是首先在較小的分區上重現。 – Blastfurnace 2012-04-03 23:40:07

+0

如果您選擇了一個體面的關鍵點,那麼在遞歸深度成爲問題之前就會耗盡內存。然後深度是數組大小的對數。 – 2012-04-03 23:42:03

回答

3

用遞歸算法解決堆棧空間用盡問題的標準方法是反覆實現它。

+0

我明白,遞歸是更好的避免,但有可能解決這個問題,我仍然使用遞歸方法嗎? – user1311596 2012-04-03 23:37:12

+0

如果數據導致問題,那麼你可以通過它們,但如果方法調用的數量是問題,我不明白你如何輕鬆解決這個問題。 – stefanB 2012-04-03 23:40:10

+0

所以不可能刪除每個遞歸調用的返回地址,除了第一個遞歸調用,我將把它存儲在一個變量和最後一個recusive調用中,這個返回地址我想與第一個調用的地址交換。對不起,我的愚蠢的問題,但我厭倦和沮喪沒有找到這個問題的答案。再次感謝你! – user1311596 2012-04-03 23:48:00

1

如果堆棧空間是一個問題,但通常不是內存,您可以使用自己的堆分配棧輕鬆地將遞歸實現轉換爲迭代實現。也就是說,不要進行遞歸函數調用,而是將您關心的參數推送到您自己的堆棧數據結構中。然後您可以遍歷堆棧並處理每組參數。

3

請注意,數組中的100000個項目什麼都不是;這隻會導致嵌套調用17個函數深:

$ echo "l(100000)/l(2)" | bc -l 
16.60964047443681173951 

這是log(N)/log(2) - 在log(2)是將其轉換爲日誌基地2

支持遞歸函數調用幾乎肯定將能夠在任何平臺處理17個嵌套呼叫。