Re: [問題] 遞迴次數有沒有上限?
直接用個範例來說明：
這個Method純粹只是為了當範例用的
當傳進去的x不等於y的時候，他會把x+1，然後繼續遞迴下去
直到x==y為止
int methodt (double x , double y)
{
if (x==y) return x;
else return Methodt(x+1,y);
}
假設，現在x = 1, y = 3
執行 methodt(1,3);
那程式會這樣跑：
1.
methodt(1,3); <= 呼叫method，建立一個methodt的「域」
2.
int methodt (double x , double y) <= 宣告了 x 跟 y 兩個變數
{ 也就是說，記憶體中多這兩個值
if (x==y) return x; 一般的IDE都會附檢視變數的功能
else return Methodt(x+1,y); 請把他找出來，看看記憶體中有
} 哪些變數
3.
int methodt (double x , double y)
{
if (x==y) return x; <= 比較 x==y ，這應該不用解釋
else return Methodt(x+1,y);
}
3.
int methodt (double x , double y)
{
if (x==y) return x;
else return Methodt(x+1,y); <= 把 x+1，再次呼叫Methodt
} 再次宣告一個域
4.
int methodt (double x , double y) <= 再次宣告 x 跟 y 兩個變數
{ 並令 x = x+1 ， y = y
if (x==y) return x; 現在記憶體中有methodt methodt兩個域
else return Methodt(x+1,y); x=1 y=3 x=2 y=3 四個變數
}
5.
int methodt (double x , double y)
{
if (x==y) return x;
else return Methodt(x+1,y); <= 再次宣告一個域
}
6.
int methodt (double x , double y)
{
if (x==y) return x; <= 到這一步時，記憶體中有3個域
else return Methodt(x+1,y); 6個變數
}
7.
int methodt (double x , double y)
{
if (x==y) return x; <= 因為條件成立，所以返回 x
else return Methodt(x+1,y);
}
8.
int methodt (double x , double y)
{
if (x==y) return x;
else return Methodt(x+1,y);
} <= 返回值後，釋放 x y 兩個變數
並刪除域，留給JVM做GC
9.
int methodt (double x , double y)
{
if (x==y) return x;
else return Methodt(x+1,y); <= 返回 3 ，以下同上
}
//=================================================================
以上是遞迴的基本步驟
可以看的到，呼叫一次Methodt就會建立一個域，並在記憶體中佔了兩個變數
有些程式的寫法可能會出問題
例如說...
Methodt(4,3);
這樣的話，程式會無止盡的遞迴下去，直到記憶體用光
跳出StackOverflowError
遇到StackOverflowError，絕大多數都是這一種狀況
另一種
是無意義的「巨大」變數
例如：
void Methodt (byte[] a)
{
//DoSomeThing
byte b = new byte[a.length];
System.arraycopy(a, 0, b, 0, a.length); <= 拷貝陣列
Methodt(b);
}
萬一那個 a 是一張5MB的圖片的話
遞迴一層就會吃掉5MB
通常跑不了幾層就會 StackOverflowError
※感謝sbrhsieh大大指正
這種狀況出現的會是 OutOfMemoryError ，而不是StackOverflowError
因為byte[]是配置在heap中，而不是stack中
※ 引述《tossakite (昱)》之銘言：
: 不好意思我是java的新手(剛學第五天...)
: 如果發問不得當真的很抱歉...
: 我目前正在寫小畫家
: 但剛剛寫油漆桶功能的時候卻遇到奇怪的問題
: 基本上我是用Depth First Search的概念寫成遞迴函數
: 從滑鼠點下去的那點作為樹根 一直向外擴散尋找需要變色的像素
: 擴散順序是先往右邊找 再往上、往左 最後往下找
: 結果測試結果發現
: 如果用鉛筆圈出一塊小面積(有測過奇形怪狀) 油漆桶都可以成功把內部著色
: 但如果面積稍微大一點(大概超過50x50個像素的話)
: 它就無法著色了
: 所以懷疑是如果遞迴呼叫太多次它就會發生問題
: 測試了一下也發現
: 如果面積太大的話 遞迴總是跑到一半就自動被強行結束(每次結束的點都不一樣)
: 可是遞迴次數應該不可能會有限制吧!?
: 上網都沒有查到這方面有什麼限制存在
: 也不太可能是演算法出錯 因為面積夠小還是可以成功著色
: 由於程式碼有點多(大概25行) 不太確定要不要PO出來
: 遞迴函數傳入的參數有三個
: 一個是BufferedImage
: 一個是跟像素數量一樣多的布林二維陣列 還有一個Point
: 難道是傳入的參數太龐大的問題?
: 如果有需要檢查程式碼的話我可以再貼出來@@
: 煩請高手解惑!!
: ----------------------------
: 對不起我不知道有錯誤訊息這種東西QQQQ
: 是下面這個嗎?
: Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError
: 它後面接了很多 at .....
: 前幾個是這樣
: at java.awt.image.DirectColorModel.getRGB(DirectColorModel.java:438)
: at java.awt.image.DirectColorModel.getRGB(DirectColorModel.java:704)
: at java.awt.image.BufferedImage.getRGB(BufferedImage.java:871)
: at painter.test2.recursive(test2.java:887)
: at painter.test2.recursive(test2.java:891)
: at painter.test2.recursive(test2.java:891)
: 之後全部都是recursive函數
: 對不起我以後會注意版規的QQ
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.233.156.129
推
03/01 23:57, , 1F
03/01 23:57, 1F
→
03/01 23:59, , 2F
03/01 23:59, 2F
→
03/02 00:50, , 3F
03/02 00:50, 3F
→
03/02 00:51, , 4F
03/02 00:51, 4F
推
03/02 01:41, , 5F
03/02 01:41, 5F
推
03/02 02:06, , 6F
03/02 02:06, 6F
→
03/02 02:09, , 7F
03/02 02:09, 7F
推
03/02 02:28, , 8F
03/02 02:28, 8F
→
03/02 09:07, , 9F
03/02 09:07, 9F
試著加這一段下去看看
static int num = 0;
int Methodt()
{
num++;
//輸出 num ，如果太多層的話，可以用 if(num%100==0)去減少輸出
int re = Methodt();
num--;
return re;
}
這樣就可以知道跑到第幾層了
我現在才發現範例的傳回值是錯的....
※ 編輯: LaPass 來自: 61.59.16.65 (03/02 11:07)
→
03/02 15:17, , 10F
03/02 15:17, 10F
推
03/02 23:36, , 11F
03/02 23:36, 11F
推
03/02 23:50, , 12F
03/02 23:50, 12F
→
03/02 23:53, , 13F
03/02 23:53, 13F
→
03/02 23:58, , 14F
03/02 23:58, 14F
→
03/03 00:04, , 15F
03/03 00:04, 15F
討論串 (同標題文章)