数组的Array.prototype.flat()方法,怎么使用尾递归来实现呢

Question

Array.prototype.flat() 方法可以将嵌套数组进行扁平化处理成一维数组,可以接受一个数字为展开的几层,默认为1层。如果不管嵌套多少层都展开可以传入一个Infinity。let arr1 = [1,2,3,4,5,[6,7,8,9,10]]arr1.flat(); // [1,2,3,4,5,6,7,8,9,10]let arr2 = [1,2,3,[4,5,6,[7,8,9,[10]]]] //这里嵌套了好几层arr2.flat(Infinity) // [1,2,3,4,5,6,7,8,9,10]// 递归实现 function flat(arr) {    if (arr.length < 1 || !arr instanceof Array) return arr;    let newArray = []    for (let i of arr.values()) {      if (i instanceof Array) {        newArray = [...newArray, ...flat(i)]      } else {        newArray.push(i)      }    }    return newArray; } let arr5 = flat([1,2,3,[4,5], [6,7,8,9,[10,11,12]]]) console.log(arr5) // [1,2,3,4,5,6,7,8,9,10,11,12]我用递归实现了一个flat(),但是每嵌套一层,都会调用一次递归函数在函数内形成一个调用帧。假如嵌套十万层就会爆栈了。 怎么用尾递归来进行优化呢?尾调用: 一个函数的最后一步返回另一个函数称之为尾调用function g1() {     return 1}function fn1() {         return g1() }fn1函数执行到最后一步调用另一个函数g1函数调用自身，称为递归。如果尾调用自身，就称为尾递归。 那么问题是,怎么使用尾递归来优化上面的递归函数呢?脑子有点笨,暂时想不出。所以求各位朋友分享下思路吧

Answer 1

每次只扁平化一次, 对结果尾递归, 直到数组中没有数组

let time = 0

function flat(arr) {

  if (arr.length === 0 || !Array.isArray(arr)) return;

  let containsArray = false;

  for (let i = 0; i < arr.length; i++) {

    if (Array.isArray(arr[i])) {

      containsArray = true;

      let before = arr.slice(0, i);

      let after = arr.slice(i + 1);

      arr = before.concat(arr[i]).concat(after)

      break;

    }

  }

  console.log(++time)

  return containsArray ? flat(arr) : arr;

}

flat([1, 2, [3, 4, 5, [6], [7]], 8, [9], [10], [11, [12]]]

最后打印:8 执行了8次

Answer 2

function flat(arr) {

  var ret = []

  var dirty = false

  arr.forEach(item => {

    if (Array.isArray(item)) {

      dirty = true

      ret.push(...item)

    } else {

      ret.push(item)

    }

  })

  return dirty ? flat(ret) : ret

}