遞迴（Recursion）的解題技巧：原理與實例

遞迴（Recursion） 最早是用在數學定義式，稱作 遞迴定義（recursive definitions），使用被定義對象的自身來為其下定義，使用被定義對象的自身來為其下定義。簡單來說，就是「自己定義自己」。

遞迴函式（recursive function）簡單來說就是在一個函式當中再去呼叫它自己

之所以能夠透過遞迴函式，是因為函式堆疊（stack）在執行時有一個特性，當某個函式呼叫另一個函式時，需要等到裡面的函式執行完產生結果後，才會繼續回來執行自己的函式內容，而這樣的情況也被稱作 後進先出（Last in First Out, LIFO）。

遞迴（recursive function）的方式有二種分別為

• 直接遞迴(Direct Recursion) ：直接在函式中呼叫函式本身
• 間接遞迴(Indirect Recursion) ：在函式中呼叫另個函式，再從另個函式呼叫原本函式

遞迴的常見應用題型有費波納契數列 (Fibonacci Sequence)、正整數階乘 (factorial)、最大公因數 (GCD)、河內塔 (Hanoi Tower)、N 個字元的排列組合等。

一、遞迴的構成條件

一個基本的遞迴函式一定要有

1. 終止條件（基本條件）
2. 遞迴條件（呼叫自己的條件）

// 初始（終止）條件為 n === 1，遞迴條件為 n !== 1。
function sum(n) {
  if (n === 1) {
    return 1;
  }
  return n + sum(n - 1);
}

// 遞迴過程
sum(5)
  5 + sum(4)
    4 + sum(3)
      3 + sum(2)
        2 + sum(1)
          return 1
        return 2 + 1   // 3
      return 3 + 3     // 6
    return 4 + 6       // 10
  return 5 + 10        // 15

事實上遞迴的時間複雜度相當高，並不會實際使用在計算中，需要搭配動態運算等方法把已經計算過的數值記錄下來，優化計算時間。

二、遞迴與迭代

遞迴可以改寫成迭代，迭代反之亦然

1. 迭代
   • 迴圈結構，是由下而上（Bottom-Up），一步步逼近答案
   • 用新值覆蓋舊值，直到滿足條件後結束，因為不保存中間值，因此不會消耗很多記憶體空間
2. 遞迴
   • 選擇結構，是由上而下（Top-Down），慢慢地將問題縮小，來求得答案
   • 將問題分解成干個子問題再回頭運算答案，因此會消耗大量記憶體空間，但程式碼簡單明瞭
   • 容易產生 堆疊溢位（stack overflow），因此非必要，不建議使用遞迴

三、例子: 費波那契數列

// EASY TC:O(2^N) SC:O(N)
// 初始（終止）條件為 n === 0 || n ===1，遞迴條件為 n !== 0 && n !== 1
function fibo(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } 
  return fibo(n-1) + fibo(n-2)
}
fibo(3)

// 遞迴過程
fibo(3)
  fibo(2) + fibo(1) 
    fibo(1) + fibo(0)
      return 0           // 0
    return 1 + 0         // 1
  return 1 + 1           // 2

圖片來源: 演算法筆記：遞迴（Recursion）

F(1) & F(0) 這就是費氏數列遞迴的 Base case，也就是停止的時機

因此找到這兩項後，就可以開始往前加總出其他項的值，而往前加總的順序如上圖。

可以求出最後時間複雜度約等於為 O(2^n)

• 每往下一層，步驟數變 2 倍
• 總共有 n 層 （空間複雜度 O(n)）
• 時間複雜度：O(2^n)

動態規劃（Dynamic programming ) 優化後的費波那契數列解法

用像是 Hash Table 來記錄已經計算過的值，那麼就可以避免把計算過的再計算一次。這時候就只有下圖中的綠色部分會被計算到，而藍色的部分就可以從 Hash Table 中來得到。

圖片來源: 用費波那契數列來入手動態規劃

// BEST TC:O(N) SC:O(1)
var fib = function(n) {
  const dp = [0, 1]
  return fibonacci(n, dp)
};

function fibonacci(n, dp) {
  if (n <= 1) return dp[n]  
  dp[n] = fibonacci(n-1, dp) + fibonacci(n-2, dp)
  
  return dp[n]
}

// 遞迴過程
fibo(3)
  fibo(2) + fibo(1)      // dp[3]
    fibo(1) + fibo(0)    // dp[2]
      return 0           // 0 = dp[0]
    return 1 + 0         // dp[1] + dp[0] = dp[2] = 1
  return 1 + 1           // dp[2] + dp[1] = dp[3] = 2

四、例子: 正整數的階乘（factorial）

// 初始（終止）條件為 n === 0，遞迴條件為 n !== 0
function factorial(n) {
  if (n === 0) {return 1;}
  return n * factorial(n - 1);
}

// 遞迴過程
factorial(4) 
  4 * factorial(3) 
    3 * factorial(2)
      2 * factorial(1)
        1 * factorial(0)
          return 1      // 1
        return 1 * 1    // 1
      return  2 * 1     // 2
    return 3 * 2        // 6
  return 4 * 6          // 24 

參考資料演算法筆記：遞迴（Recursion）JavaScript 學演算法（二十二）- 遞迴 Recursion遞迴 (Recursive) 介紹與經典題型演算法筆記系列 — Dynamic programming 動態規劃Dynamic Programming Explanation with Fibonacci 用費波那契數列來入手動態規劃