使用遞歸溢出堆棧的方法有哪些? 我有一個這樣的方式使用遞歸溢出堆棧
#include <iostream>
void func()
{
int arr[100500];
func();
}
int main()
{
func();
std :: cin.ignore(); std :: cin.get();
return 0;
}
但我不喜歡它。
使用遞歸溢出堆棧的方法有哪些? 我有一個這樣的方式使用遞歸溢出堆棧
#include <iostream>
void func()
{
int arr[100500];
func();
}
int main()
{
func();
std :: cin.ignore(); std :: cin.get();
return 0;
}
但我不喜歡它。
在main()
你叫func()
然後調用func()
(本身),然後調用func()
(本身)等
每次調用一個函數,指針被壓入堆棧。堆棧是有限的內存量,最終會填滿,然後你得到一個stack overflow
。
由於您的程序將無休止地調用func()
堆棧將會快速填充。
還要注意,本地變量arr
也將被分配到堆棧上。這將更快地填滿堆棧。
當遞歸太深時,可能導致堆棧溢出,因爲函數本地變量和返回地址存儲在堆棧中。在你的情況下,你有無限遞歸,也就是說,你沒有一個條件來阻止func()調用自己,因此你正在溢出堆棧。
沒有定義的限制,它取決於您運行遞歸的語言和體系結構。
不知道,謝謝! :) – 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));
}
讀者做練習:給定一個智能編譯器,可以使用多少優化來最小化遞歸。
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