遞迴的基本結構以及注意事項

直接用個範例來說明:

這個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)
{
if (x==y) return x;
else return Methodt(x+1,y);
}

宣告了 x 跟 y 兩個變數。也就是說,記憶體中多這兩個值。
一般的IDE都會附檢視變數的功能,請把他找出來,看看記憶體中有哪些變數

3.

int methodt (double x , double y)
{
if (x==y) return x;
else return Methodt(x+1,y);
}

比較 x==y ,這應該不用解釋

4.

int methodt (double x , double y)
{
if (x==y) return x;
else return Methodt(x+1,y); <= 把 x+1,再次呼叫Methodt
}

再次宣告一個域

5.

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 四個變數
}

6.

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

通常跑不了幾層就會OutOfMemoryError

 

Comments are closed.

Welcome , today is 星期二, 2017/11/21