使用遞歸溢出堆棧

-2

使用遞歸溢出堆棧的方法有哪些？我有一個這樣的方式使用遞歸溢出堆棧

#include <iostream> 

void func() 
{ 
    int arr[100500]; 
    func(); 
} 

int main() 
{ 
    func(); 

    std :: cin.ignore(); std :: cin.get(); 

    return 0; 
}

但我不喜歡它。

來源

2012-02-09 Andrew

int arr [1005000000000000000000000000];' – 2012-02-09 07:45:26

int a [1 << 31]; //如果編譯器允許 – loxxy 2012-02-09 07:48:04

@Andrew。你的問題？你說你不喜歡它，但是在對一個答案的評論中，你認爲它不是上班。 – stefaanv 2012-02-09 08:08:10

在main()你叫func()然後調用func()（本身），然後調用func()（本身）等

每次調用一個函數，指針被壓入堆棧。堆棧是有限的內存量，最終會填滿，然後你得到一個stack overflow。

由於您的程序將無休止地調用func()堆棧將會快速填充。

還要注意，本地變量arr也將被分配到堆棧上。這將更快地填滿堆棧。

來源

2012-02-09 07:47:13

我知道它:)但是，當我測試（在MSVC++ 2010）時，沒有跡象表明堆棧已滿... – Andrew 2012-02-09 07:52:15

測試究竟是什麼？ – 2012-02-09 07:54:09

我的第一篇文章中的代碼。 – Andrew 2012-02-09 07:57:21

當遞歸太深時，可能導致堆棧溢出，因爲函數本地變量和返回地址存儲在堆棧中。在你的情況下，你有無限遞歸，也就是說，你沒有一個條件來阻止func（）調用自己，因此你正在溢出堆棧。

沒有定義的限制，它取決於您運行遞歸的語言和體系結構。

來源

2012-02-09 07:47:52 m0skit0

不知道，謝謝！ :) – m0skit0 2012-02-09 07:54:36

你可能想閱讀這個問題的答案，http://stackoverflow.com/questions/2630054/does-c-limit-recursion-depth。 C++語言沒有定義堆棧深度的限制。另一方面，您的操作系統將強制限制堆棧佔用的空間量。 – aalpern 2012-02-09 07:59:09

@LuchianGrigore你在哪裏找到這個定義的下限？我從來沒有見過它，也沒有聽說過它，我無法在標準中找到它。（當然，在標準中找東西並不總是微不足道的。） – 2012-02-09 08:23:37

由於無限遞歸，填充堆棧非常容易;

void func() { func(); }

會做得很好。任何函數調用都會將信息壓入堆棧（至少是一個返回地址），所以如果在某個時刻它不停止調用它自己，它將用完堆棧。

我發現很難明白爲什麼你會不喜歡這樣的功能，就像你所做的那樣。它可以滿足需要，而且速度很快。

但是，優化可能會導致編譯器將函數變成無限循環，因爲很容易發現它不起任何作用。

如果你想真正做什麼事情的一個功能的演示，

int factorial(int n) { return n<= 0 ? 1 : factorial(n - 1) * n; }

就是一個很好的例子，給定一個適當大的值n，並沒有編譯器優化（也可能發現了尾巴的機會遞歸併將其轉化爲循環）。

如果做不到這一點，試試這個（阿克曼的功能，遞歸函數不是原始地遞歸，也不會受到在最後一行優化的一個例子。

unsigned int A(unsigned int m, unsigned int n) 
{ 
    if (m == 0) return n + 1; 
    if (n == 0) return A(m - 1, 1); 
    return A(m - 1, A(m, n - 1)); 
}

讀者做練習：給定一個智能編譯器，可以使用多少優化來最小化遞歸。

來源

2012-02-09 08:18:41

使用遞歸溢出堆棧

回答

相關問題