在學習JS的路上意外接觸到了遞迴的概念，一開始覺得這是什麼鬼東西，迴圈用的好端端的，為什麼需要學習難懂的遞迴？

雖然學會遞迴不會讓你搖身一變成為JS大師，但卻可以讓自己在思考問題的解決方式時多了一種敘述方式，不好奇嗎？

以下先用輕鬆的例子認識一下遞迴。

日常生活舉例

舉例及圖片來源：freeCodeCamp: Recursion in Programming

想像今天要去買珍珠奶茶，結果店家前大排長龍，你想知道還要等多少個人才能輪到你點餐，這時你可能會側身往前望向櫃檯前的第一個人然後開始數數，依序數排在前面有多少人，這的確是最直覺的方法，但很累（是有多懶）。

除此之外，其實可以往前拍拍前一位在排隊的大叔，問說：你前面還有幾位在等啊？可能大叔也不知道自己還要等幾位才輪到他，於是也拍拍前面的少女，重複同樣的問題，如此重複下去直到站在櫃檯前點餐的學生不耐地轉過頭說：沒看到我正在點餐嗎？下一位就換你了！這時排隊人龍裡的每個人就可以依序告訴後面的人自己是排在第幾位了。這樣的懶人方式就是遞迴的精神（別鬧了）

定義與其基本形式

維基百科介紹遞迴是這麼說的:

在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法

在程式語言中則是透過一個函式呼叫函式本身也就是所謂的遞迴函式來實現遞迴的概念

不過如果函式不斷呼叫自己，不是會形成無窮迴圈嗎？所以必須再加上一個終止條件，綜合上述就會形成下列的遞迴基本形式：

1. A simple base case (or cases) — a terminating scenario that does not use recursion to produce an answer
2. A recursive step — a set of rules that reduces all successive cases toward the base case.

回到一開始買珍珠奶茶的例子，我們來看看真實生活的行為如何對應到遞迴的形式

1. 終止條件：問到目前正在點餐的客人為止
2. 遞迴步驟：不斷地詢問前一位等待的人是第幾位是遞迴步驟

有了基本概念後，來實際看看程式碼吧～

遞迴經典例子

嘗試理解遞迴時，最常看到的範例就是高中數學學過的階乘啦。
階乘的定義是所有小於及等於該數的正整數的積，記為n!
例如：3! = 3 * 2 * 1 = 6

運用遞迴的概念則階乘的計算可以簡化成 n! = n * (n - 1)！
轉換成程式碼如下：

function factorial(n) {
  if (n <= 1) {
    return 1;
  } else { 
    console.log(`${n} * factorial(${n - 1})`); // 此行程式碼只為了觀察遞迴的過程，不是遞迴的一部份 
    return n * factorial(n - 1);
  }
}

const result = factorial(5);
console.log(result);  

// 5 * factorial(4)
// 4 * factorial(3)
// 3 * factorial(2)
// 2 * factorial(1) --> 終止條件 
//120

至於電腦是如何實現遞迴的必須再研究call stack，待日後再來好好深入研究啦～

參考資料：
Understanding Recursion in Programming
遞迴 (電腦科學)
遞迴的美麗與哀愁