簡介
遞迴是程式設計中一個很強大的概念，指的是函式自己呼叫自己。
一開始可能有點難懂，但只要掌握了基本觀念，它就會成為解決複雜問題的實用工具。
在這篇教學中，我們會用簡單易懂的範例來認識 JavaScript 中的遞迴。
什麼是遞迴？
當一個函式直接或間接呼叫自己時，就稱為遞迴。
它和迴圈很像，但會把問題拆解成更小、更容易處理的子問題。
範例 1：倒數
我們先從一個簡單的範例開始吧：倒數函式。
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
在這個範例中：
-
基本情況：當
num小於或等於 0 時，函式會印出 "Blastoff!" 並停止呼叫自己。
-
遞迴情況：函式會印出目前的
num，然後用num - 1再呼叫自己一次。
範例 2：階乘
接著，我們來看一個遞迴的經典範例：計算一個數字的階乘。
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
在這個範例中：
-
基本情況：當
n是 0 或 1 時，函式回傳 1。
-
遞迴情況：函式會把
n乘上n - 1的階乘。
核心概念
基本情況
每個遞迴函式都至少要有一個基本情況，也就是讓函式停止呼叫自己的條件。
如果沒有基本情況，遞迴就會無止境地持續下去，最後導致堆疊溢位。
遞迴情況
遞迴情況定義了函式如何用更小或更簡單的問題版本來呼叫自己。
遞迴的優缺點
優點：
- 對某些問題來說是優雅的解法。
- 類似數學歸納法的概念。
缺點：
- 效率可能不如疊代解法。
- 遞迴太深時可能導致堆疊溢位。
結論
遞迴是一項很有用的技巧，能把複雜的問題拆解成更小、更容易處理的子問題，讓問題變得簡單一些。
想用 JavaScript 寫出有效的遞迴解法，理解基本情況和遞迴情況是關鍵。
延伸閱讀：
說明
你經營一間披薩店，提供三種披薩：
- Margherita：$7
- Caprese：$9
- Formaggio：$10
如果顧客想要，可以加購不限數量的額外選項：一份 "ExtraSauce" 是 $1，一份 "ExtraToppings" 是 $2。
你的任務是撰寫程式碼，協助顧客算出他們需要支付的費用。
計算披薩的價格
第一個引數是披薩的名稱，後面可以接不限數量的加購選項。請計算這個披薩的價格（以美元為單位）。
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
計算整筆訂單的總價
你的函式會收到一個由 PizzaOrder 組成的陣列，並應回傳整筆訂單的總價（以美元為單位）。
每個 PizzaOrder 都有一個 pizza 屬性，也就是披薩的名稱，以及一個 extras 屬性，也就是加購選項的陣列。
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
你會發現，這個函式沒辦法用遞迴來寫，因為其中一個測試包含大量訂單，會引發 Maximum call stack size exceeded。
別擔心，這是刻意的。試著用命令式迴圈來實作這個函式吧！
你有很多選擇，例如使用 reduce 或 for 迴圈，但不限於這些。
當 JavaScript 翻譯員在執行 JavaScript 程式碼時，會用一種稱為「堆疊」的資料結構，記錄自己進入了（開始呼叫）哪些函式。
當函式回傳（結束）時，就會從堆疊中移除。
不過，這個堆疊的大小是有限的。
最常見的錯誤，是寫出永遠不會結束的遞迴函式。
每一次呼叫都會被放上堆疊，但在它回傳之前，又有另一次呼叫被放上堆疊。
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
這個錯誤的堆疊追蹤會不斷顯示同一行，這很合理，因為函式呼叫了自己。
雖然在大多數情況下這沒什麼實際用途，但你可以試著找出這個堆疊能長到多高。
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
對於同步遞迴函式所造成的呼叫堆疊錯誤，只有兩種可行的解法：
- 確保函式在達到堆疊上限之前回傳，通常是新增或修正基底情況。
- 把遞迴函式改寫成命令式迴圈，這樣會直接執行迴圈主體，不必進入函式，也就不會增加堆疊。
學習練習
