介紹

前面我們了解關於迴圈的應用，就是透過條件判斷持續執行區塊程式，遞迴的觀念與它有一點相似。

遞迴顧名思義不斷迴轉，是在函數中呼叫自己本身並將其回傳值當成新引數傳入的技術。這部分好處在於它能夠解決迴圈比較難處理的複雜問題，如本章的停機問題與下一章節會介紹的經典問題 --河內塔。不過使用遞迴最需要注意的是它遞迴之次數，我們通常會稱作深度 ”depth”

遞迴最為人詬病是過多的呼叫本身而造成回傳值不好去控制，雖然程式碼簡潔大大增加了其可讀性(readability)，不過沒有提供一個跳出呼叫的出口，反而會造成程式難以去理解。

正式介紹前，這邊簡單的舉例一下利用遞迴執行階乘 :

public int fac(int num) {
    if (num != 1) {
      return num * fac(num-1);         
    } 
		else
	    return 1;
}
public class void main(String[] args){
	System.out.println(fac(4));           //求 4! = 24
}

• 程式解析 : 引數4傳入，進入函數第一個條件判斷，接著再次呼叫自己傳遞3進去，而原本的4就儲存於記憶體中，等待最後retuen 1 → 開始一個一個乘上去。
  

遞迴(Recursion)

我們再將遞迴運用式子的模式條列出來解釋 :

public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);         //Using sum(k-1) calling itself repeatly 
    } 
    else {
      return 0;
	}
}

假設我們傳入 20 進去 ，函數就會執行連續的遞迴直到 k ≤ 0時

20 + sum(19)
20 + ( 19 + sum(18) )
20 + ( 19 + ( 18 + sum(17) ) )
...
20 + 19 + 18 + 17 + 16 + 15 +14 + … + sum(0)
20 + 19 + 18 + 17 + 16 + 15 +14 + … + 0 = 210

• 透過條列式的方式，我們可以發現其實編譯器在執行遞迴時，是先將一開始的數字儲存，而後續進來的數字，則放在前一個數字上面。最後其會將最上面的回傳值拿出來，並開始一個一個回傳數值，結束後就是我們要的答案。這種結構，我們叫做堆疊(stack)
  

停機問題(Halting Condition)

就像迴圈，當我們沒有設定給它一個停止條件，它就會形成一個無限迴圈，畫面會一直跑不會停…
遞迴我們稱為「停機」(Halting Condition)。命令遞迴在甚麼時候停止。

static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);     
    } 
	else {
      return end;
    }
  }

• 程式解析 : 假設我們傳入start = 10, end = 20.此範例會進行10-20的連加，而停機條件出現在當最後end 以 10傳入參數儲存時，只會回傳數值 10，停止執行此遞迴。這就是我們成稱為的停機問題。

以上內容若有錯誤，煩請不吝嗇指教，謝謝您!!!