實作遞迴函式

一些簡單的遞迴範例。

簡述

關於遞迴的套路：

• 幾乎都是在呼叫 function 的時候「把參數值更新」來做出像迴圈一樣的效果。
• 要求出 A 的值，就先找出 A-1 的值
• 一直「往前」找，找到最後的終止條件為止。

求出某數的 N 次方

function power(base, exponent) {
  if (exponent > 0) {
    return base * power(base, exponent-1)
  } else {
    return 1
  }
}
var result = power(2, 31)
console.log(result) // 2147483648

不懂得話參考一下你自己亂畫的圖：

求出階層

function factorial (n) {
  if (n > 1) {
    return n * factorial(n-1)
  } else {
    return 1
  }
}
var result = factorial(5)
console.log(result)

費式數列

function fab(n) {
  if(n < 2) {
    return n
  } else {
    return fab(n-1) + fab(n-2)
  }
}
console.log(fab(10))

清除 DOM 的文字節點

/*
  cleanJunkNodes 會接收一個節點：
  1. 取得該節點下的所有子節點
  2. 判斷子節點的值
  3. 如果是沒用的節點就刪掉
*/
function cleanJunkNodes (node) {
  // 遍歷所有子節點
  for (let i=0; i<node.childNodes.length; i++) {
    // 存取第 i 個子節點
    let child = node.childNodes[i]
    // 如果是註解 or 文字節點（只有空白字元）
    if 
    (
      child.nodeType === 8
      || 
      child.nodeType === 3 && !/\S/.test(child.nodeValue)
    ) 
    {
      // 刪除子節點
      node.removeChild(child)
      // 往前退一格（因為長度變短了）
      i--
    }
    else if (child.nodeType === 1) {
      // 如果子節點也是元素，丟到遞迴 cleanJunkNodes 清除垃圾節點
      cleanJunkNodes(child)
    }
  }
}

二分搜尋法

// 要遞迴的 function 
function binarySearchRecursively(array, targetElement, start, end) {
  // 左邊界 > 右邊界
  if (start > end) {
    return -1
  }

  // 中間位置（無條件捨去，取偏左邊那點）
  const middle = (start + end) >> 1

  /*
    目標 = 中間那個數字：
    找到數字了，直接回傳位置
    
    目標 > 中間的數字：
    代表前面的數字不用看了，把 start 設為中間位置往右移一位（+1）
    
    目標 < 中間的數字：
    代表後面的數字不用看了，把 end 設為中間位置往左移一位（-1）
  */
  if (targetElement === array[middle]) {
    return middle
  } else if (targetElement > array[middle]) {
    // 更新 start 後，遞迴 binarySearchRecursively
    return binarySearchRecursively(array, targetElement, middle + 1, end)
  } else {
    // 更新 end 後，遞迴 binarySearchRecursively
    return binarySearchRecursively(array, targetElement, start, middle - 1)
  }
}
// 用來執行 binarySearchRecursively
function binarySearch(array, targetElement) {
  return binarySearchRecursively(array, targetElement, 0, array.length-1)
}

const numbers = [1, 3, 24, 33, 57, 88, 99, 101]
console.log(binarySearch(numbers, 25))  // -1
console.log(binarySearch(numbers, 24))  // 2

快速排序法

function quickSort(arr) {
  // 停止點，當 arr 長度為 1 或沒有元素了
  if (arr.length <= 1) {
    return arr
  }

  // 基準點 index
  const pivotIndex = Math.floor(arr.length / 2)
  // 基準點 number
  const pivotNumber = arr.splice(pivotIndex, 1)[0]
  // 比基準點小的數列
  let samllerNumbers = []
  // 比基準點大的數列
  let biggerNumbers = []

  // 把小的放到 samll，大的放到 bigger
  for (let i=0; i<arr.length; i++) {
    if (arr[i] < pivotNumber) {
      samllerNumbers.push(arr[i])
    } else {
      biggerNumbers.push(arr[i])
    }
  }
  // 把小的跟大的都丟到 quickSort 遞迴，最後要跟 pivot 結合起來
  return quickSort(samllerNumbers).concat([pivotNumber], quickSort(biggerNumbers))

}
const numbers = [5, 44, 23, 3, 42, 4, 2]
console.log(quickSort(numbers))

壓平陣列

function flatten(arr) {
  // 儲存壓平後的陣列
  const result = []
  // 遍歷陣列元素
  arr.forEach(item => {
    // 如果元素是陣列，遞迴這個 function
    if(Array.isArray(item)) {
      // 呼叫自己
      const flattenArray = flatten(item)
      // 把壓平後的陣列 push 回結果
      flattenArray.forEach(item => result.push(item))
    } else {
      result.push(item)
    }
  })
  // 回傳結果
  return result
}

console.log(flatten([1, 2, 3]))  // [1, 2, 3]
console.log(flatten([1, 2, 3, [1, 2], [3, 4], 5])) // [1, 2, 3, 1, 2, 3, 4, 5]
console.log(flatten([1, 2, 3, [1, [2]], [3, 4, [5]], 6]))  // [1, 2, 3, 1, 2, 3, 4, 5, 6]
console.log(flatten(['1,', 2, 3]))  // ['1,', 2, 3]

實作 DOM 的 closest 方法

function closestRecursive(node, className) {
  // 如果節點不存在 or 不包含 class
  // 回傳 null 代表找到底了
  if (!node || !node.classList) {
    return null
  } 
  // 如果符合 className，代表找到了
  if (node.classList.contains(className)) {
    return node
  }
  // 還沒找完，繼續往上一層找
  return closestRecursive(node.parentNode, className)
}

類似 setInterval 的 setTimeout

function log(i) {
  console.log(i)
  setTimeout(() => {
    log(++i)
  }, 1000)
}
log(1)