重写数组递归函数，中间有递归输出

Question

如何用尾递归重写这个函数？不知道可不可以，因为递归调用需要在数组的中心应用。

const weave = array =>
  array.length <= 2
    ? array
    : [ array[0], ...weave(array.slice(2)), array[1] ]

我编写了一个函数来查找数字的因子对，其中因子对的形式为 [ [1, x], [2, x/2], ... ]（假设 x 是偶数，在这种情况下）。我想展平数组并在 O(n) 时间内对其进行排序。

const getFactors = x => weave(getFactorPairs(x).flat())

注：纯属熏陶。上面的函数和 array.flat().sort() 都足够完美。

Answer 1

以真正的 Stack-Overflow-as-rubber-duck 方式，解决方案变得显而易见，同时在问题中写下我对答案的最佳尝试，如此明显以至于我几乎懒得发帖。

const weave = (array, pre = [], post = []) =>
  array.length <= 2
    ? [ ...pre, ...array, ...post ]
    : weave(
        array.slice(2),
        [ ...pre, array[0] ], 
        [ array[1], ...post ]
      )

Answer 2

另一种选择是使用 continuation-passing style。此技术通常用于以递归形式实现 tail-call。

const identity = x =>
  x

const weave = (a, then = identity) =>
  a.length < 2
    ? then(a)
    : weave(a.slice(2), r => then([a[0], ...r, a[1]]))
      
console.log(weave("abcdefg")) // [a,c,e,g,f,d,b]
weave("abcdefg", console.log) // [a,c,e,g,f,d,b]

Trampoline technique mentioned in the comments can be implemented in various ways. This example is modelled after Clojure's loop/recur 蹦床界面。

此处它已应用于您的代码。我将数组输入换成了字符串，这样可以更轻松地可视化输出。 weave 在不到 150 毫秒的时间内处理 100 万个字符串。

function recur(...values) {
  return Object.assign(values, {recur})
}

function loop(f) {
  let result = f()
  while (result?.recur === recur)
    result = f(...result)
  return result
}

const weave = (input = []) =>
  loop((a = input, pre = "", post = "") =>
    a.length < 2
      ? pre + a + post
      : recur(a.slice(2), pre+a[0], a[1]+post))
      
console.time("weave 1M")
document.write(weave(`<  >  <  >`.repeat(100000)))
console.timeEnd("weave 1M")

重写数组递归函数，中间有递归输出

Rewrite array recursive function with recursive output in middle

arrays

recursion

tail-recursion