JavaScript recursive zip function Could the performance of this function be optimized (without making the code much longer)?

The function zips two arrays into another.

function zip(p,q) {
  if( p.length &gt; 1 || q.length &gt; 2) {
    return ([[p[0],q[0]]]).concat(zip(p.slice(1),q.slice(1)));
  } else {
    return ([[p[0],q[0]]]);
  }
}



How exactly does the slice work? Is it immutable, like getting the tail in Haskell? 
What values are inside the value returned by .concat()? Are these copy-constructed values from references, or are these references and are copied when a new array is constructed with the call to .concat()?
Recursive memory hog!!

I have to say that this is not at all a practical way to zip two arrays. 

Recursive functions are huge memory hogs in JS if done badly

In Javascript calling a function adds a minimum of about 1 - 1.5K to the call stack, and you create copies each array of each call, ouch..

Test

I ran your function giving it two 8Mb array (1,000,000 numbers each) and it crashed Chrome. Something I would expect to do using a function like zip.

Crashed at 0.01% complete

Canary 65 devtools has a live performance monitor, so I ran that and I watched memory climb in less than a second to 1GB befor the browser interrupted and paused the code. The heap is full and the function was only 97 iterations in (approx 0.01% complete).

Why the memory usage?

Your use of Array.slice is the reason. Slice creates a shallow copy of each array. So if you have an array of size 100 and slice at 1 you now have two arrays for a total of 199 items.

Lets follow the recursion with 2 3 itemed arrays


function zip(p,q) {
  if( p.length &gt; 1 || q.length &gt; 2) {
    return ([[p[0],q[0]]]).concat(zip(p.slice(1),q.slice(1)));
  } else {
    return ([[p[0],q[0]]]);
  }
}



Make the call

zip([1,2,3],[4,5,6]);

zip(p.slice(1),q.slice(1));       // create 2 copies 2 bytes each
&gt;&gt; zip(p.slice(1),q.slice(1))     // create 2 copies 1 bytes each
&gt;&gt; &gt;&gt;  return ([[p[0],q[0]]]);    


At this point there are arrays [3,6], [3], [6], [2,3], [5,6], [1,2,3], [4,5,6]

return ([[p[0],q[0]]]).concat( &lt;&lt; &lt;&lt;


This is when you hit peek memory use, just before the above return you add another array [1,4,3,6] so you have stored in memory 18 references

return ([[p[0],q[0]]]).concat( &lt;&lt;
End.


Result is an array with 6 references.

Calculating memory use

You memory usage assuming same sized arrays is

len = array.length; // both arrays are the same size

totalReferences = (len / 2) * (len + 1) * 2 + 6


So for 2 array of size 100

(100 / 2) * (100 + 1) * 2 + 6 === 10,106


And for larger

1,000   === 1,001,006
10,000  === 100,010,006
100,000 === 10,000,100,006


How to improve.

Can Tail Call Optimisation (TCO) help?

TCO basically lets you call a function without adding a new context to the call stack. This makes calling a function almost as fast as running inline code. This would be the single best thing to have happened to the language for decades (and its only decades old), if it happened :(. 

Javascript ES6 spec has (the very anticipated and needed) TCO but it remains the only unimplemented ES6 feature on Chrome, Firefox, and Edge. Reason?? I believe too many pages are kept running due to call stack overflow error, TCO prevents this and thus a bad recursion function blocks the page rather than throws an error. 

Don't hold your breath waiting for TCO, for now its not going to help.

The only solution

In reality without TCO you can not safely do this via recursion. The call stack size is much smaller than the max array size. If you do recursion you would have to limit the array sizes, but even then you can not know how deep you are already in the call stack when you start, so there is no safe way to do this (Yes all recursive functions in javascript are fatally flawed, until TCO)

Quick simple and low memory use.

function zip(a, b) {
    const min = Math.min(a.length, b.length);
    var i, j, c;
    c = [];
    i = j = 0;
    while (j &lt; min) {  
        c[i ++] = a[j];
        c[i ++] = b[j ++];
    }
    if (a.length &lt; b.length) { [a, b] = [b, a] }
    while (j &lt; a.length) { c[i ++] = a[j ++] }
    return c;
}