Rewrite array recursive function with recursive output in middle-CodePudding

How can I rewrite this function with tail-recursion? I don't know if it's possible because the recursive call needs to be applied in the center of the array.

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

I wrote a function that finds the factor pairs of a number, where the pairs are of the form [ [1, x], [2, x/2], ... ] (assuming x is even, in this case). I want to flatten the array and sort it in O(n) time.

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

Note: This is purely for my edification. Both the function above and array.flat().sort() are perfection performant enough.

CodePudding user response：

In true Stack-Overflow-as-rubber-duck fashion, the solution became obvious while writing my best attempt at an answer within the question, so obvious that I almost didn't bother posting.

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

CodePudding user response：

Another option is to use continuation-passing style. This technique is commonly used to achieve a tail-call in recursive forms.

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]