接下來想要緩慢的把自己的 CS 相關基礎補上，多多接觸寬廣的技術知識，就先從遞迴開始吧！

🐳 遞迴的種類

如果一個 function 裡面有 self-calling 的敘述，便稱為遞迴，遞迴概略可以分為三個種類，分別是：

  • Direct Recursion
  • Indirect Recursion
  • Tail Recursion

下面舉一些簡單的例子來說明這三個遞迴。

🦀 Direct Recursion

Direct Recursion，直接遞迴，應該蠻好理解的。如果某個 function 在 function 內部呼叫自己，就可以稱為直接遞迴。可以參考下面的 psuedo code：

1
2
3
4
5
6
7
8
void directRecursionFunction()
{
  // some code...

  directRecursionFunction();

  // some code...
}

🦀 Indirect Recursion

Indirect Recursion，間接遞迴，意思是指多個 module 之間，彼此互相呼叫，形成 calling cycle。例如：假設目前有三個 function：module A、module B、module C，這三個 function 彼此互相呼叫，便會形成間接遞迴，如下圖：

flowchart LR
  A[module A] --> B[module B]
  B --> C[module C]
  C --> A

像上面那種 function 互相 call 來 call 去，互相高度依賴的狀況（高耦合），盡量不要在實際開發中寫出來，會很可怕。

🦀 Tail Recursion

Tail Recursion，尾端遞迴，其實是直接遞迴的一種，只是在 recursion 之後，下一個可執行的敘述就是 END 敘述。會特別把這個種類分出來是因為這種遞迴可以在 compiler 裡面做到最佳化。（最佳化的意思，某種程度上可以理解成「將遞迴改成非遞迴」）

🐳 Recursion v.s. Iteration(Non-recusrion)

  • 任何問題的解法必定可以用兩種演算法去解決：遞迴與非遞迴。
  • 遞迴與非遞迴演算法兩者可以互相轉換
    • 遞迴改為非遞迴，有標準 SOP
    • 非遞迴改回遞迴，沒有標準 SOP（需要靈感）

示意圖

graph TB
  A -. 要修改的話有SOP .-> C
  C -. 必存在,但沒有SOP .-> A
  A[Recurstive Algo] --> B[Problem]
  C[Non-recursive Algo] --> B[Problem]

比較表

遞迴 非遞迴
程式碼 較精簡 較冗長
區域變數、暫存變數 使用很少或是沒有 使用量多
表達問題的能力 powerful weak
除錯 困難 容易
程式執行時間 較久，比較沒有效率 較短，較有效率
memory stack 空間 需要額外的 stack 空間支持，所以執行時需要較多的動態空間 無需 stack support

🐳 題目練習

🦀 Factorial N! 階乘

Question 1: Write an Interative function Fac(N) or pseudo code for N!

1
2
3
4
5
6
7
function fac(n) {
  let result = 1;
  for (let i = 1; i <= n; i++>) {
    result = result * i;
  }
  return result;
}

Question 2: Write a Recursive function Fac(N) or pseudo code for N!

先把階乘的遞迴數學定義寫出來：

然後再寫出遞迴的程式碼：

1
2
3
4
5
6
7
function fac(n) {
  if (n === 0) {
    return 1;
  } else {
    return fac(n-1) * n;
  }
}

解遞迴相關問題的訣竅：先想出遞迴的數學定義，再把數學定義轉換成程式碼！

🦀 Fibonacci Number

Definition

Question 1: Write a Recurisive function for Fib(N)

1
2
3
4
5
6
7
8
9
function fib(n) {
  if (n === 0) {
    return 0;
  }
  if (n === 1) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

Quesiton 2: Write a Interative function for Fib(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function fib(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    let a = 0;
    let b = 1;
    let c;
    for (let i = 2; i <= n; i++) {
      c = a + b;
      a = b;
      b = c;
    }
    return c;
  }
}

🦀 Greatest Common Divisor (GCD) 最大公因數

Definition

用輾轉相除法來計算兩個數字（A, B）的最大公因數，定義如下：

Write the recursive code for GCD(A, B)

1
2
3
4
function gcd(a, b) {
  if (a % b === 0) return b;
  return gcd(b, a % b);
}

🦀 Tower of Hanoi 河內塔

題目敘述

有三個柱子，假設分別叫做 A、B、C，其中 A 柱子上有 n 個大小不同的盤子，這些盤子從上到下按照大小排放，最上面的盤子最小，最下面的盤子最大，現在要把這些盤子從 A 柱子移到 C 柱子，但必須遵守以下規則：

  1. 每次只能移動一個盤子
  2. 大的盤子不能放在小的盤子上面

請把所有的移動步驟都 print 出來。

解題思路

1
2
3
4
5
6
7
8
9
       A            B           C

       │            │           │
       │            │           │
       │            │           │
1    ┌─┼─┐          │           │
2   ┌┼┼┼┼┼┐         │           │
3  ┌┼┼┼┼┼┼┼┐        │           │
  ─┴───────┴─   ────┴────   ────┴────

先從例子開始想，假設目前有 A、B、C 三個柱子，然後有 3 個盤子在 A 柱子上面，則步驟如下：

  1. move disk 1 from A to C
  2. move disk 2 from A to B
  3. move disk 1 from C to B
  4. move disk 3 from A to C
  5. move disk 1 from B to A
  6. move disk 2 from B to C
  7. move disk 1 from A to C

把步驟分成三個區塊來看：

  1. 第 1. ~ 3. 步驟是把 1 ~ 2 號的盤子都先從 A 柱子移到 B 柱子
  2. 第 4. 步驟是把最後一個第 3 號盤子直接從 A 柱子移到 C 柱子
  3. 接下來是把 B 柱子上的盤子都移到 C 柱子

例外情況：如果只有一個盤子的話，就直接從 A 柱子搬到 C 柱子就可以了。

1
2
3
4
5
6
7
8
9
function hanoi(n, from, to, via) {
  if (n === 1) {
    console.log(`move disk 1 from ${from} to ${to}`);
  } else {
    hanoi(n - 1, from, via, to); // 先把 n - 1 個盤子都移到中間的柱子
    console.log(`move disk ${n} from ${from} to ${to}`); // 把最下面的盤子移到目標柱子
    hanoi(n - 1, via, to, from); // 再把剩下的 n - 1 個盤子移到目標柱子
  }
}

河內塔的遞迴定義

把上面提到的步驟用數學式來表示， 表示移動 個盤子時程式所需的執行次數，如果解出 就表示解出了這個 function 的時間複雜度：

且

解 ，用展開代入法：