javascript - Tail Call Optimizing recursive function

Question

This is a function which deep-flattens an array

const deepFlatten = (input) => {
  let result = [];
  input.forEach((val, index) => {
    if (Array.isArray(val)) {
      result.push(...deepFlatten(val));
    } else {
      result.push(val);
    }
  });
  return result;
};

During a discussion, I was told it is not memory efficient, as it might cause stack overflows.

I read in http://2ality.com/2015/06/tail-call-optimization.html that I could potentially re-write it so that it is TCO-ed.

How would that look like and how could I measure it's memory usage profile?

Answer 1

tail calls in general

I've shared another functional approach to flattening arrays in JavaScript; I think that answer shows a better way to solve this particular problem, but not all functions can be decomposed so nicely. This answer will focus on tail calls in recursive functions, and tail calls in general

In general, to move the recurring call into tail position, an auxiliary function (aux below) is created where the parameters of the function holds all the necessary state to complete that step of the computation

const flattenDeep = arr =>
  {
    const aux = (acc, [x,...xs]) =>
      x === undefined
        ? acc
        : Array.isArray (x)
          ? aux (acc, x.concat (xs))
          : aux (acc.concat (x), xs)
    return aux ([], arr)
  }
        
const data = 
  [0, [1, [2, 3, 4], 5, 6], [7, 8, [9]]]
  
console.log (flattenDeep (data))
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]