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

直接用個範例來說明：

這個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

 


 © 2024 - 二三往事