遞歸演算法棧溢出JAVA

① java遞歸的優點缺點

遞歸好處：代碼更簡潔清晰，可讀性更好
遞歸可讀性好這一點，對於初學者可能會反對。實際上遞歸的代碼更清晰，但是從學習的角度要理解遞歸真正發生的什麼，是如何調用的，調用層次和路線，調用堆棧中保存了什麼，可能是不容易。但是不可否認遞歸的代碼更簡潔。一般來說，一個人可能很容易的寫出前中後序的二叉樹遍歷的遞歸演算法，要寫出相應的非遞歸演算法就比較考驗水平了，恐怕至少一半的人搞不定。所以說遞歸代碼更簡潔明了。

遞歸壞處：由於遞歸需要系統堆棧，所以空間消耗要比非遞歸代碼要大很多。而且，如果遞歸深度太大，可能系統撐不住。

個人覺得：非必要時不遞歸

② java排序演算法中，快速排序慢好多，還容易爆棧，求指教

• 代碼沒問題

• 我今天也遇到一樣的問題

• 猜測是因為快排遞歸創建了很多棧，當數據量過大時就棧溢出

• 我的解決方法是自己也寫了一個快速排序非遞歸的方法

• 但是實際耗費的時間仍然不如其他演算法
  

③ 遞歸累加時，出java.lang.StackOverflowError了，怎麼辦

這么遞歸下去肯定會棧溢出。
如果單純的想要1-10000的累加至於這么麻煩么？

累加的效率問題：
目前有下面兩種方法：
方法一：
long sum = 0;
for(int i = 0;i < value;i++)
{
sum += i;
}

方法二：
long sum = 0;
sum = (value + 1) * value / 2;

當value值等於10000，使用方法一，運行10次有4次會產生15毫秒左右耗時，使用方法二，運行10次無耗時產生。
當value值等於100000，使用方法一，運行10次有5次會產生15毫秒左右耗時，使用方法二，運行10次無耗時產生。
當value值等於1000000，使用方法一，運行10次有10次會產生31毫秒左右耗時，使用方法二，運行10次無耗時產生。
......
以此類推，方法一累加計數的效率和方法二相比，隨著value值的級數遞增，效率相應下降。

測試代碼：
public class SimpleArithmetic
{
public static void main(String[] args)
{
SimpleArithmetic sa = new SimpleArithmetic();
long sum = 0;
long time = 0;
long curTime = System.currentTimeMillis();
System.out.println("curTime=" + curTime);

//sum = sa.getSumCycle(1000000);
sum = sa.getSumNotCycle(1000000);
System.out.println(sum);

long endTime = System.currentTimeMillis();
System.out.println("endTime=" + endTime);

time = endTime - curTime;
System.out.println(time);
}

private long getSumCycle(long value)
{
long sum = 0;

for(long i = 1;i <= value;i++)
{
sum += i;
}

return sum;
}

private long getSumNotCycle(long value)
{
long sum = 0;
sum = (value + 1) * value / 2;
return sum;
}
}

④ JAVA中能夠實現方法的遞歸調用嗎如何實現

能 遞歸函數即自調用函數，在函數體內直接或間接的調用自己，即函數的嵌套是函數本身。遞歸調用又分為直接調用和間接調用
直接調用funca(){ ...... funca();};間接調用；funca(){ ...... funcb();}funcb(){ ..... funca(); .....} 漢諾塔源碼public class HanoiY { void Move(char chSour,char chDest){ System.out.println("Move the top plate of "+chSour+"-->"+chDest); } void Hanoi(int n,char chA,char chB,char chC) { if(n==1) Move(chA,chC); else { Hanoi(n-1,chA,chC,chB); this.Move(chA,chC); Hanoi(n-1,chB,chA,chC); } } public static void main(String[] args) { int n=Integer.parseInt(args[0]); HanoiY han=new HanoiY(); han.Hanoi(n,'A','B','C'); } }

⑤ java中遞歸演算法是什麼怎麼算的

一、遞歸演算法基本思路：

Java遞歸演算法是基於Java語言實現的遞歸演算法。遞歸演算法是一種直接或者間接調用自身函數或者方法的演算法。遞歸演算法實質是把問題分解成規模縮小的同類問題的子問題，然後遞歸調用方法表示問題的解。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形式，從而使我們的編碼大大簡化，然而遞歸的思維確實跟我們的常規思維相逆的，通常都是從上而下的思維問題，而遞歸趨勢從下往上的進行思維。

二、遞歸演算法解決問題的特點：

【1】遞歸就是方法里調用自身。

【2】在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。

【3】遞歸演算法代碼顯得很簡潔，但遞歸演算法解題的運行效率較低。所以不提倡用遞歸設計程序。

【4】在遞歸調用的過程中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸演算法設計程序。

【5】在做遞歸演算法的時候，一定把握出口，也就是做遞歸演算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口就是一個條件，當滿足了這個條件的時候我們就不再遞歸了。

三、代碼示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代碼執行流程圖如下：

此程序中n=5就是程序的出口。

⑥ java棧內存溢出怎麼解決

第一對所有的代碼包括頁面中的java代碼都進行一遍徹底的回顧檢查，
1.對那些靜態(static)的對象要特別留神，特別是類型為Map,List,Set的，靜態的變數會一直駐存在內存中，生命周期比較長，不會被垃圾器回收。
2．對於代碼，要審查是否生成了大量的冗餘的對象，還有一些邏輯業務處理的類，
演算法是否過於復雜，調整演算法，對於代碼認真審查，再仔細重構一遍代碼，能提高代碼質量，提高程序運行穩定性。
3.Java中的內存溢出大都是因為棧中的變數太多了。其實內存有的是。建議不用的盡量設成null以便回收，多用局部變數，少用成員變數。
1），變數所包含的對象體積較大，佔用內存較多。
2），變數所包含的對象生命周期較長。
3），變數所包含的對象數據穩定。
4），該類的對象實例有對該變數所包含的對象的共享需求。
4．在我的程序中對靜態變數的優化後，使程序佔用內存量至少提升了5k-10k。所以也不容忽視。
第二還有就是String類相關的東西：
1．字元串累加的時候一定要用StringBuffer的append方法，不要使用+操作符連接兩個字元串。差別很大。而且在循環或某些重復執行的動作中不要去創建String對象，因為String對象是要用StringBuffer對象來處理的，一個String對象應該是產生了 3個對象（大概是這樣：））。
2．字元串length()方法來取得字元串長度的時候不要把length放到循環中，可以在循環外面對其取值。(包括vector的size方法)。特別是循環次數多的時候，盡量把length放到循環外面。
int size = xmlVector.size();
for (int i = 2; i < size; i++) {
。。。
}
3 寫代碼的時候處理內存溢出
try{
//do sth
....
}catch (outofmemoryerror e){//可以用一個共通函數來執行.
system.out.print (「no memory! 」);
system.gc();
//do sth again
....
}
4.對於頻繁申請內存和釋放內存的操作,還是自己控制一下比較好,但是System.gc()的方法不一定適用，最好使用finallize強制執行或者寫自己的finallize方法。 Java 中並不保證每次調用該方法就一定能夠啟動垃圾收集，它只不過會向JVM發出這樣一個申請，到底是否真正執行垃圾收集，一切都是個未知數。

⑦ Java如何在不使用遞歸的情況下導致棧溢出

歸 調用,在不斷的壓 棧 過程中,造成 棧 容量超過1m而 導致 溢出 .2,解決方案:方... 演算法正確的情況下,使用過程中會出現堆 棧溢出 的話,可以通過修改PLUS函數,

⑧ Java-java產生StackOverflowError的原因是什麼

棧溢出。Java裡面每個線程都有獨立的、固定大小的棧空間， Java在解釋執行的時候採用的是棧式的架構。 方法調用、方法內的局部變數都是在棧空間申請的。 空間的大小依賴於JDK版本，JDK1.6應該是512K，超過了這個空間就會產生StackOverFlow。
死循環本身是不會StackOverflow的，只有無限遞歸的時候會出現。原則上循環嵌套次數本身是沒有限制的，限制的是佔用的棧空間，如果你的方法里定義了很多很多變數，棧空間就會用完得比較快。如果你的軟體不是很龐大，那麼你的程序中出現了無限的遞歸的情況可能產生這個錯誤。

⑨ 同樣是調用遞歸演算法，快速排序文件過大時棧溢出，而歸並排序則不會，怎麼解決

不知道你在哪裡看到的快速排序，雖然寫得這么糾結，但是結果還是對的。快速排序跟歸並排序的最大區別是歸並排序需要額外的空間，這個空間你是在堆里分配的，而快速遞歸不需要申請一個O(n)空間是因為通過函數棧保存了一些中間數據，正常來說當你元素很多時比如大於1M，函數棧肯定會溢出的，因為函數棧一般默認大小就是1M，函數棧大小是可以設置的，怎麼設置函數棧大小你可以查網路。這些或許你都知道，不過你的遞歸演算法也有點問題，因為你中間元素key就取了第一個元素，這會使得出現很多的遞歸浪費大量的棧空間，比如元素本來就有序的以你的演算法時間復雜度為T(n) = T(n-1) + n，這個時間復雜度是O（n*n），遞歸次數為n，正常情況遞歸次數應該是log（n）次的，你遞歸了時間不說棧空間就需要很大，所以這也可能是你棧溢出的一個可能。快速排序的中間元素key不能去第一個元素就行了，即使隨機取一個都比你取第一個好多了。這里有我之前寫的一個快速排序
struct my_traits<T*>
{
typedef T value_type;
}
template<class BidirectIterator>
void IterSwap(BidirectIterator i,BidirectIterator j)
{
if(*i == *j) return;
typename my_traits<BidirectIterator>::value_type temp = *i;
*i = *j;
*j = temp;
}
template<class T>
void InsertSort(T *first,T *last)
{
for(T *i = first + 1;i < last;++i)
{
T value = *i;
T *j = 0;
for(j = i;j - 1 >= first&&*(j - 1) > value;--j)
*j = *(j - 1);
*j = value;
}
}
template<class T>
T Median3(T*first,T*last)
{
T * middle = first + (last - first) / 2;
last--;
if(*first > *middle)
IterSwap(first,middle);
if(*first > *last)
return *first;
if(*middle < *last)
return *middle;
return *last;

}
template<class T>
T* Partition(T *first,T *last,T pivot)
{
while(true)
{
while(*first < pivot) ++first;
--last;
while(*last > pivot) --last;

if(first > last) return first;
IterSwap(first,last);
++first;
}
}

template<class T>
void QuikSort(T *first,T *last)
{
if(last - first >= 4)
{
T *cut = Partition(first,last,Median3(first,last));
QuikSort(first,cut);
QuikSort(cut,last);
}
else
{
InsertSort(first,last);
}
}