数组的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 = 0function flat(arr) {&nbsp; if (arr.length === 0 || !Array.isArray(arr)) return;&nbsp; let containsArray = false;&nbsp; for (let i = 0; i < arr.length; i++) {&nbsp; &nbsp; if (Array.isArray(arr[i])) {&nbsp; &nbsp; &nbsp; containsArray = true;&nbsp; &nbsp; &nbsp; let before = arr.slice(0, i);&nbsp; &nbsp; &nbsp; let after = arr.slice(i + 1);&nbsp; &nbsp; &nbsp; arr = before.concat(arr[i]).concat(after)&nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; }&nbsp; }&nbsp; console.log(++time)&nbsp; 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) {&nbsp; var ret = []&nbsp; var dirty = false&nbsp; arr.forEach(item => {&nbsp; &nbsp; if (Array.isArray(item)) {&nbsp; &nbsp; &nbsp; dirty = true&nbsp; &nbsp; &nbsp; ret.push(...item)&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; ret.push(item)&nbsp; &nbsp; }&nbsp; })&nbsp; return dirty ? flat(ret) : ret}