遞迴

發表於 分類於

遞迴

函式呼叫函式自己的行為，稱為 遞迴、或是 遞歸 。

先來看一下在 MDN 上的說明

函式呼叫函式自己的行為，稱為遞迴、或是遞歸。它主要用於解決含有子問題的問題。
遞迴函式會收到兩個輸入：結束遞迴的基本情況（base case）或是延續遞迴的遞迴情況（recursive case）。

也就是說，函式透過呼叫自己的行為，在有限的條件下，透過判斷 if...else 執行循環的運算或程式碼。

改寫九九乘法表

通常要寫一個簡單的九九乘法表，最直覺的是會想到使用 for 迴圈，我們先來看一下原本的寫法

1
2
3
4
5
for (let i = 1; i < 10; i++) {
  for (let k = 1; k < 10; k++) {
    console.log(`${i} x ${k} = ${i * k}`);
  }
}

但是這樣就會變成雙層 for 迴圈，看起來相當冗長，萬一要再多加一層變成 1 x 2 x 3 = 6，這樣就會需要再多加一層，無論是在撰寫或是閱讀上都顯得複雜。

接下來看一下改成遞迴的寫法

1
2
3
4
5
6
function print99(a, b) {
  console.log(`${a} x ${b} = ${a * b}`);
  if (b < 9) return print99(a, b + 1);
  if (a < 9) return print99(a + 1, 1);
}
print99(2, 1);

如果要再多加一層也是沒問題的

1
2
3
4
5
6
7
8
9
10
11
12
function print99(a, b, c) {
  console.log(`${a} x ${b} x ${c} = ${a * b * c}`);
  if (c < 9) return print99(a, b, c + 1, 1);
  if (b < 9) return print99(a, b + 1, 1, 1);
  if (a < 9) return print99(a + 1, 1, 1, 1);
}
print99(1, 2, 3);

// 1 x 2 x 3 = 6
// 1 x 2 x 4 = 8
// 1 x 2 x 5 = 10
// ...

陣列遞迴展開

再來看一個經點案例，試著使用遞迴來展開多層陣列

1
2
3
4
5
6
7
8
9
10
11
12
13
const arry = [1, 2, [3, 4, [5, 6, [7, 8]]]];
const result = [];
function flatArray(ary) {
  ary.forEach((item) => {
    if (!Array.isArray(item)) {
      result.push(item);
    } else {
      flatArray(item);
    }
  });
  return result;
}
console.log(flatArray(arry));