淺談 JS 中的遞歸

一、遞歸

遞歸（英語：Recursion）

在數學與計算機科學中，是指在函數的定義中使用函數自身的方法

在函數內部，可以調用其他函數。如果一個函數在內部調用自身本身，這個函數就是遞歸函數

其核心思想是把一個大型複雜的問題層層轉化爲一個與原問題相似的規模較小的問題來求解

一般來說，遞歸需要有邊界條件、遞歸前進階段和遞歸返回階段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回

下面實現一個函數 pow(x, n)，它可以計算 x 的 n 次方

使用迭代的方式，如下：

function pow(x, n) {
  let result = 1;

  // 再循環中，用 x 乘以 result n 次
  for (let i = 0; i < n; i++) {
    result *= x;
  }
  return result;
}

使用遞歸的方式，如下：

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

pow(x, n) 被調用時，執行分爲兩個分支：

             if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

也就是說pow 遞歸地調用自身 直到 n == 1

爲了計算 pow(2, 4)，遞歸變體經過了下面幾個步驟：

  1. pow(2, 4) = 2 * pow(2, 3)

  2. pow(2, 3) = 2 * pow(2, 2)

  3. pow(2, 2) = 2 * pow(2, 1)

  4. pow(2, 1) = 2

因此，遞歸將函數調用簡化爲一個更簡單的函數調用，然後再將其簡化爲一個更簡單的函數，以此類推，直到結果

二、尾遞歸

尾遞歸，即在函數尾位置調用自身（或是一個尾調用本身的其他函數等等）。尾遞歸也是遞歸的一種特殊情形。尾遞歸是一種特殊的尾調用，即在尾部直接調用自身的遞歸函數

尾遞歸在普通尾調用的基礎上，多出了 2 個特徵：

在遞歸調用的過程當中系統爲每一層的返回點、局部量等開闢了棧來存儲，遞歸次數過多容易造成棧溢出

這時候，我們就可以使用尾遞歸，即一個函數中所有遞歸形式的調用都出現在函數的末尾，對於尾遞歸來說，由於只存在一個調用記錄，所以永遠不會發生 "棧溢出" 錯誤

實現一下階乘，如果用普通的遞歸，如下：

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5,6) // 120

如果n等於 5，這個方法要執行 5 次，才返回最終的計算表達式，這樣每次都要保存這個方法，就容易造成棧溢出，複雜度爲O(n)

如果我們使用尾遞歸，則如下：

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5,6) // 120

可以看到，每一次返回的就是函數本身，不帶上一個函數的參數，也就不需要儲存上一個函數了。尾遞歸只需要保存一個調用棧，複雜度 O(1)

二、應用場景

遞歸的場景有很多，列舉幾個我們常見的，如

數組求和

function sum(arr, total) {
    if(arr.length === 1) {
        return total
    }
    return sum(arr, total + arr.pop())
}

使用尾遞歸優化求斐波那契數列

function factorial2 (n, start = 1, total = 1) {
    if(n <= 2){
        return total
    }
    return factorial2 (n -1, total, total + start)
}

數組扁平化

let a = [1,2,3, [1,2,3, [1,2,3]]]
// 變成
let a = [1,2,3,1,2,3,1,2,3]
// 具體實現
function flat(arr = [], result = []) {
    arr.forEach(v => {
        if(Array.isArray(v)) {
            result = result.concat(flat(v, []))
        }else {
            result.push(v)
        }
    })
    return result
}

數組對象格式化

let obj = {
    a: '1',
    b: {
        c: '2',
        D: {
            E: '3'
        }
    }
}
// 轉化爲如下：
let obj = {
    a: '1',
    b: {
        c: '2',
        d: {
            e: '3'
        }
    }
}

// 代碼實現
function keysLower(obj) {
    let reg = new RegExp("([A-Z]+)", "g");
    for (let key in obj) {
        if (obj.hasOwnProperty(key)) {
            let temp = obj[key];
            if (reg.test(key.toString())) {
                // 將修改後的屬性名重新賦值給temp，並在對象obj內添加一個轉換後的屬性
                temp = obj[key.replace(reg, function (result) {
                    return result.toLowerCase()
                })] = obj[key];
                // 將之前大寫的鍵屬性刪除
                delete obj[key];
            }
            // 如果屬性是對象或者數組，重新執行函數
            if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') {
                keysLower(temp);
            }
        }
    }
    return obj;
};

參考文獻

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/xS8XH9XKWhBSUDtRsSrauQ

猜你喜歡