軟體工程師職涯升級計畫啟動！立即預約職涯諮詢、履歷健檢或模擬面試👈，為您的加薪做好準備！
遞迴函式（Recursive Function）是一種在函式內部呼叫自己的技術，它讓複雜的問題能被分解成更小的、重複的子問題來解決。其中一個最經典的範例就是費波那契數列。
費波那契數列是什麼？
費波那契數列（Fibonacci Sequence）是一個特殊的數列，從 0 和 1 開始，後續的每一項都是前兩項的和。它的數學定義如下：- 第 0 項：F(0)=0
- 第 1 項：F(1)=1
- 第 n 項：F(n)=F(n−1)+F(n−2)
根據這個規則，我們可以列出數列的前幾項：0,1,1,2,3,5,8,13,21,34,55,...
遞迴程式碼實作
將上述數學定義轉換成 JavaScript 程式碼非常直觀。我們可以建立一個 fib 函式來計算第 n 項費波那契數。
function fib(n) {
// 終止條件（Base Case）：
// 當 n 為 0 或 1 時，直接返回其定義值
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
// 遞迴呼叫：將問題拆解成兩個較小的子問題
return fib(n - 1) + fib(n - 2);
}
// 範例：計算第 5 項
console.log(fib(5)); // 輸出 5
這個程式碼的核心是兩個部分：
- 遞迴條件（Recursive Step）：return fib(n - 1) + fib(n - 2)，這讓函式不斷地呼叫自己，將問題分解。
- 終止條件（Base Case）：if (n === 0) 和 if (n === 1)，這兩個條件是遞迴停止的時機。如果沒有終止條件，遞迴將會無限循環下去，導致程式崩潰。
遞迴呼叫的流程：以樹狀圖解析
當我們呼叫 fib(5) 時，它會像樹一樣層層展開。
從圖中可以看到，每次函式呼叫都會繼續往下分解，直到遇到 fib(1) 或 fib(0) 這些終止條件。一旦達到終點，程式會從最底層開始，將結果層層往上傳遞並加總，最終得到 fib(5) 的結果。這個從下往上、由內而外計算的過程，正是因為函式呼叫是藉由**函式堆疊（Call Stack）來管理的，其遵循後進先出（Last In, First Out, LIFO）**的原則。
動態規劃：告別重複計算的低效率
你可能已經注意到，傳統的遞迴解法雖然直觀，但效能極差。以費波那契數列為例，當我們計算 fib(5) 時，fib(3) 被計算了兩次，fib(2) 甚至被計算了三次。這種對相同子問題的重複計算，正是導致時間複雜度高達 O(2n) 的主因。
動態規劃（Dynamic Programming, DP）正是為了解決這類問題而生的強大技術。其核心思想很簡單：「把已經計算過的部分儲存下來！」
動態規劃的適用條件
一個問題若要能用動態規劃解決，通常需要滿足以下三個性質：
- 最優子結構（Optimal Substructure）：一個問題的最優解，是由其子問題的最優解所構成。例如，要求費波那契數列第 n 項的最佳解，只需知道第 n−1 和第 n−2 項的最佳解。
- 無後效性（No Aftereffect）：當前狀態的確定，不會受到後續決策的影響。也就是說，我們在計算第 n 項時，只需依賴第 n−1 和第 n−2 項的結果，而它們是如何被計算出來的，對我們來說並不重要。
- 重疊子問題（Overlapping Subproblems）：問題可以被分解成重複的子問題。費波那契數列就是一個典型的例子，fib(3) 和 fib(2) 在計算 fib(5) 的過程中多次被呼叫。
動態規劃解法：兩種常見模式
動態規劃通常有兩種實現方式，核心都是利用**記憶化（Memoization）**來避免重複計算。
1. 自上而下（Top-down）遞迴 + 記憶化
這種方式依然使用遞迴，但會額外使用一個陣列或雜湊表來儲存已經計算過的結果。在每次遞迴呼叫前，先檢查結果是否已被計算過。
// 使用陣列來儲存計算結果
const memo = [];
function fibDP_topDown(n) {
// 如果結果已經被計算過，直接返回
if (memo[n] !== undefined) {
return memo[n];
}
// 終止條件
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
// 遞迴計算並將結果存入 memo
memo[n] = fibDP_topDown(n - 1) + fibDP_topDown(n - 2);
return memo[n];
}
console.log(fibDP_topDown(5)); // 輸出 5
// 這時 memo 陣列會長這樣：[0, 1, 1, 2, 3, 5]
2. 自下而上（Bottom-up）迭代
這種方式通常使用**迴圈（Iteration）**來從最底層的子問題開始計算，並逐步向上推導。
function fibDP_bottomUp(n) {
if (n === 0) {
return 0;
}
if (n === 1) {
return 1;
}
// 使用陣列來儲存計算結果
const dp = [0, 1];
// 從第 2 項開始，逐步計算到第 n 項
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
console.log(fibDP_bottomUp(5)); // 輸出 5
無論是哪種方式，透過儲存中間結果，我們將時間複雜度從指數級的 O(2n) 大幅優化到線性的 O(n)，這正是動態規劃的強大之處。
結語
遞迴和動態規劃是演算法領域中兩個核心且相輔相成的概念。遞迴提供了一個優雅且直觀的解題思路，讓我們能夠將大問題分解為小問題，但其潛在的效能問題不容忽視。而動態規劃則是在遞迴的基礎上進行優化，透過記憶化來避免重複計算，將低效的指數級複雜度提升到高效的線性或多項式級，是解決許多複雜問題的強大武器。掌握這兩種技巧，將能讓你更有效率地應對各種程式設計挑戰。
