Re: [問題] 遞迴次數有沒有上限?

[LaPass (LaPass)]

直接用個範例來說明：
這個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
推 tossakite:原來如此!!! 很感謝你的詳細說明~:D
→ tossakite:看來只好放棄美麗的遞迴了QQ  用迴圈寫DFS感覺好難....
→ LaPass:其實我覺得你想辦法把幾個比較「笨重」的參數移到外面，應
→ LaPass:該就可以解決問題了....
推 tossakite:我努力把參數縮到剩一個Point物件  還是畫不了大面積...
推 tossakite:我把它寫成完全不用傳參數 函數裡也沒有宣告任何新東西
→ tossakite:竟然還是StackOverFlow...!!  請問所謂的域很耗資源嗎?
推 eieio:你 50x50 的區域，寫 recursive 的話就有可能有 250 層
→ LaPass:之前除這種錯時，跑到一萬層都沒問題....

試著加這一段下去看看
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)
→ gameking:會不會是電腦設備的問題  記憶體太小?
推 tossakite:蛤真的嗎?  可是4G應該還算OK吧@@
推 tossakite:它最高可以畫到6000左右個像素  但很奇妙的是  超過6000
→ tossakite:個像素的話 它幾乎遞迴跑4000多次就停了(但偶爾會8000多
→ tossakite:阿應該要計算層才對= =  等一下我重寫...
→ tossakite:結果是  極限是在2068~2074層之間很規律的週期變化...