在堆上分配vs在遞歸函數中分配堆棧

Question

當我定義一個遞歸函數時，在堆上分配局部變量是否更好/更安全，然後在函數返回前清理它們，而不是將它們分配到堆棧上。嵌入式系統上的堆棧大小非常有限，當遞歸運行太深時，存在堆棧溢出的危險。

Answer 1

答案取決於您的應用程序域和您的平臺的具體情況。 「嵌入式系統」是一個模糊的術語。 A big oscilloscope running MS Windows or Linux位於光譜的一端。它大部分可以像普通PC一樣編程。他們不應該失敗，但如果他們這樣做，只需重新啓動它們。

另一方面是安全關鍵領域的控制器。考慮these Siemens switches，它必須在毫秒內在所有情況下作出反應。失敗不是一種選擇。他們可能不運行Windows。可用資源有限。編程規則和程序在這裏有很大的不同。

現在讓我們來看看你擁有的選項，遞歸（或不是！）與動態或自動內存分配。

性能方面，堆棧更快，所以它是首選。動態分配還涉及一些記賬開銷，如果數據單元很小，則記賬費用很大。並且可能會出現內存碎片問題，這在自動內存中不會發生（儘管導致碎片的場景 - 對象的不同生命週期 - 如果沒有動態分配，可能無法直接解決）。

但的確，在某些系統中堆棧大小比堆大小要小得多;您必須閱讀有關係統上的內存佈局。示波器將有很多內存和大堆棧;電源開關不會。

如果您擔心內存不足，我會按照Christian的建議完全避免遞歸，而是使用循環。迭代可能只是保持內存使用平坦。此外，遞歸總是使用堆棧空間，例如，返回地址和值。動態分配「本地」變量的想法只對更大的數據結構有意義，因爲您仍然必須將指向數據的指針作爲自動變量，這也會佔用堆棧空間（並且會增加總體內存佔用量） 。

通常，在資源有限的系統上，限制程序使用的最大資源非常重要。時間也是一種資源;動態分配使得實時幾乎不可能。

應用程序域規定了安全要求。在安全關鍵領域（起搏器！），程序絕對不能失敗。除非這個計劃是微不足道的，否則這個理想是不可能實現的，但是很大的努力要靠近。在其他領域中，程序可能會在無法處理的情況下以定義的方式失敗，但它不能以默默無聞或未定義的方式失敗（例如，通過覆蓋數據）。例如，不是動態分配未知數量的數據，而只是爲數據定義一個固定大小的預定義數組，並使用數組中的元素來代替邊界檢查。

Answer 2

當我定義一個遞歸函數時，在堆上分配局部變量，然後在函數返回之前清理它們比在堆棧上分配它們更好/更安全。

您同時擁有C和C++標記。它是一個有效的問題，但我只能對C++發表評論。

在C++中，儘管其效率略低，但它更好地使用堆。這是因爲如果您用完堆內存，new可能會失敗。在失敗的情況下，new會拋出異常。但是，堆棧空間不足不會導致異常，並且是其原因之一alloca is frowned upon in C++。

Answer 3

我認爲一般來說你應該避免在嵌入式系統中進行遞歸，因爲每次函數被調用時都會將返回地址推送到堆棧。這可能會導致意外溢出。嘗試切換到循環。

回到你的問題，雖然mallocing會更慢但更安全。如果沒有堆空間，則malloc將返回一個錯誤，並且可以安全地清理內存。由於malloc的速度很慢，因此速度很大。

如果您知道您預期會有多少次迭代，您可以選擇將所需變量的數組進行分配。這樣你只能使用malloc一次，這樣可以節省時間，而且不會冒着意外填滿堆或堆棧的風險。你也只會留下一個變量來釋放。