遞迴種類

遞迴分為直接遞迴和間接遞迴兩種:
直接遞迴: 直接在函式內再次呼叫本身函式

function fn1() {
    fn1();
}

間接遞迴: 函式呼叫另外的函式，再從另外函式呼叫原來的函式

function fn1() {
    fn2();
}

function fn2() {
    fn1();
}

比較: 遞迴 vs. 迴圈

1. 遞迴執行效率較迴圈慢，因為需要進行函式呼叫，同時儲存計算後的資料也比較消耗記憶體空間
2. 在求解時需要使用到堆疊特性的資料結構時，使用遞迴的話通常程式碼會比較簡潔
3. 遞迴比較不用儲存狀態，且更像 Declarative 的形式，而迴圈常用變數儲存當前遍歷計算的結果

常見的遞迴應用 & 範例題:

遞迴真的蠻常見的，像以下的案例都有使用到:

1. JSON.parse & JSON.stringify
2. document.getElementById & 查找 DOM 元素
3. 物件遍歷

何時適合使用遞迴?

和分治法、和樹資料結構相關的狀況

範例題1. 多維陣列扁平化

// flatten([1, 2, 3, [4, 5] ]) // [1, 2, 3, 4, 5]
// flatten([1, [2, [3, 4], [[5]]]]) // [1, 2, 3, 4, 5]
// flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]]) // [1, 2, 3]

// 用 for loop
function flatten(arr){
    let result = [];
    for(let i = 0; i < arr.length; i++) {
        if(Array.isArray(arr[i])) {
            result = result.concat(flatten(arr[i]));
        } else {
            result.push(arr[i]);
        }
    }  
    return result;
}

// 用 reduce
function flatten(arr){
    return arr.reduce((result, ele) => {
        if(Array.isArray(ele)) {
            return result.concat(flatten(ele));
        }
        return result.concat(ele);
    }, [])
}

範例題2. 判斷字串是否為回文

所謂的回文就是一個字串從左邊讀到右邊結果和從右邊讀到左邊的內容都一樣，這樣就是回文。
ex:
level，Race car，Do geese see God?
因此問題就是: 給定一個字串，然後判斷此字串是否為回文，若是回文就回傳 true，不是就回傳 false

了解問題後就來實作吧!

我們可以把思考邏輯寫下來:

1. 要判斷回文的話，我們就要將字串的第一個字元和最後一個字元作判斷是否一樣，第二個字元和倒數第二個字元作判斷...以此類推，在作判斷時要記得忽略非英文字的字元。
2. 就算同個字母，但大小寫不同，依舊可判定為回文。

思考完畢，先建立一個判斷函式並完成部分內容:

1. 共有三個參數，一個記錄字串，一個記錄前面判斷的字元位置，一個記錄後面判斷的字元位置
2. 接著設定最後一個字元 end 的值，字串最後一個字元的索引一定是字串的長度減1(第1個字元索引0)，因此便完成 end 值設定
3. 當字串長度為1個或0個字元時，我們可以當作回文，直接回傳true，而當 start 大於等於 end 位置代表所有的字元都已經判斷過

// 設定start索引為0，end索引未知，故為null
function isPalindrome(str, start = 0, end = null) {
  // 先初始化end的值
  if (end === null) end = str.length - 1
  
  if(str.length < 2) { // 只有一個或零個字元，歸類為回文
    return true;
  } else if (end <= start) { // 全部字元都比較完成時
    return true;
  } else {
  
  }
}

完成剩下 else{} 的部分:

1. 先將 start 和 end 都轉為大寫，目的是因為回文無視大小寫，前面讀到後面和後面讀到前面一樣就好。
2. 接著我們判斷 start 和 end 是否是字母，不是的話就往後/往前移動一個字元，透過遞迴再此呼叫判斷函式
3. 之後當判斷的兩個字母不相同時，代表肯定不是回文，因此回傳 false
4. 如果兩個字母相同時，就讓 start 到後一個字元位置，end 到前一個字元位置，重新用遞迴呼叫判斷函式一次

const ALPHABET = "ABCDEFGHIJKLMNOPQRSTVWXYZ"

function isPalindrome(str, start = 0, end = null) {
  if (end === null) end = str.length - 1
  
  if(str.length < 2) {
    return true;
  } else if (end <= start) {
    return true;
  } else {
    // 將要比較的字母都轉大寫
    let c1 = str.charAt(start).toUpperCase()
    let c2 = str.charAt(end).toUpperCase()
    // c1,c2 不是字母的話，必須移動到後一個/前一個字母，並再呼叫一次isPalindrome()
    if (!ALPHABET.includes(c1)) {
      return isPalindrome(str, start + 1, end)
    } else if (!ALPHABET.includes(c2)) {
      return isPalindrome(str, start, end - 1)
    } else if (c1 !== c2) { // 兩個比較字母不同，肯定不是回文
      return false
    } else {
      return isPalindrome(str, start + 1, end - 1) // 讓start到後一個字元位置，end到前一個字元位置，重新執行函式
    }https://github.com/a90100/javascript-data-structure/blob/master/day10-recursion.js
  }
}

完成判斷函式了，完整的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day10-recursion.js

範例題3. 將巢狀物件的屬性值為數字的值都轉為字串

function stringifyNumbers(obj) {
  let newObj = {}
  for (let i in obj) {
    if (typeof obj[i] === 'number') {
      newObj[i] = obj[i].toString();
    } else if (typeof obj[i] === 'object' && !Array.isArray(obj[i])) {
      console.log(obj[i])
      newObj[i] = stringifyNumbers(obj[i])
    } else {
      newObj[i] = obj[i];
    }
  }
  return newObj;
}

let obj = {
    num: 1,
    test: [],
    data: {
        val: 4,
        info: {
            isRight: true,
            random: 66
        }
    }
}

console.log(stringifyNumbers(obj));

/*
{
    num: "1",
    test: [],
    data: {
        val: "4",
        info: {
            isRight: true,
            random: "66"
        }
    }
}
*/

這次的介紹到此結束。明天我們將會來介紹樹 Tree 此種資料結構!

推薦閱讀文章

遞迴 (Recursion)

tail call optimization 可以研究一下，用來優化遞迴