数组的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

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
}

Answer 2

首先，只要是递归就可能爆，如果不想爆要么指定深度结束，要么换别的方法实现。

function fn1(deep) {
    if (deep > 0) {
        deep--
        return fn1(deep)
    }
    return;
}


fn1(100000)

栗子

//循环实现
function flat(arr) {
    if (arr.length < 1 || !arr instanceof Array) return arr;
    let newArray = []

    while (arr.length > 0) {
        let nextTask = [];

        for (let i of arr) {
            if (i instanceof Array) {
                nextTask = nextTask.concat(i);
            } else {
                newArray.push(i)
            }
        }
        arr = nextTask;
    }
    return newArray;
}

//生成深度测试数组 用于验证爆栈
let testArray = Array(100000).fill().map((d, i) => ([i])).reduce((acc, cur) => {
    cur[1] = acc;
    return cur;
})

console.log(flat(testArray))

Answer 3

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

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次