When does the call stack get set up in Javascript?

Question

In trying to solve the following problem:

Generate all combinations of an array of string.
Ex: Input: ['A', 'T', 'C', 'K']
Output: [
  'ATCK', 'ATC', 'ATK',
  'AT',   'ACK', 'AC',
  'AK',   'A',   'TCK',
  'TC',   'TK',  'T',
  'CK',   'C',   'K',
  ''
]

I have the following code:

function getSpellableWords(arr) {
    const res = [];
    // helper(arr, res, 0, '');
    helper(arr, res, 0, []);
    return res;
}

function helper(arr, res, i, slate) {
  const char = arr[i];
  console.log(i, 'i')
  if(i === arr.length) {
    res.push(slate.join(''));
    return;
  }

  // slate = slate + char;
  slate.push(char)
  console.log(slate, 'slate')
  helper(arr, res, i+1, slate);
  slate.pop()

  helper(arr, res, i+1, slate);
}

getSpellableWords(['A', 'T', 'C', 'K']);

My questions is:

If I remove the following lines in the code:

helper(arr, res, i+1, slate);

Once i is equal to 5 (which is the array.length), the code will stop after it pushes slate into res. However, if I leave that line in, a call stack is set up and so i will go up from 1->5, then pop out gradually to 4 then 3 then back to 4 and so on. Why does that happen?

Clarification: So I understand that for each recursion call, another i variable is generated. However, I was expecting the second recursion call to also generate i from 1->4 again, but this time instead of incrementing it linearly, there's backtracking going on as well. Why wasn't there backtracking in the first call, and why does the second call generate the rest of the results when the first call only generates the first result?

Answer 1

Each recursive call of helper will indeed add a level on the call stack, so that when a recursive call returns back to its caller, that calling code can continue with its own local execution context.

Each execution of helper has its own execution context, which includes a local variable i which is only visible to that execution context. It only plays a role at that level in the call stack.

Note that the helper code never changes the value of its i variable. It gets initialised with whatever value is passed as third argument when it gets called, and that is the only value it will ever have.

The change to i that you notice is in fact no change. Every different value you see for i is in fact about a different variable that just happens to have the same name.

Here is a little schema on the life of these i variables for when the res variable has length 2 (just to not make it too lengthy!):

helper(arr, res, 0, []); // The initial call
    +--------top level helper execution context----+
    | i = 0                                        |
    | ....                                         |
    | slate.push(char)                             |
    | helper(arr, res, i+1, slate);                |
    |      +---nested helper execution context---+ |
    |      | i = 1                               | |
    |      | ....                                | |
    |      | slate.push(char)                    | |
    |      | helper(arr, res, i+1, slate);       | |
    |      |      +--deepest exec. context-----+ | |
    |      |      | i = 2                      | | |
    |      |      |  ...                       | | |
    |      |      | res.push(slate.join(''));  | | |
    |      |      | return;                    | | |
    |      |      +----------------------------+ | |
    |      | // i is still 1                     | |
    |      | slate.pop()                         | |
    |      | helper(arr, res, i+1, slate);       | |
    |      |      +----------------------------+ | |
    |      |      | i = 2                      | | |
    |      |      |  ...                       | | |
    |      |      | res.push(slate.join(''));  | | |
    |      |      | return;                    | | |
    |      |      +----------------------------+ | |
    |      | // i is still 1                     | |
    |      +-------------------------------------+ |
    | // i is still 0                              |
    | slate.pop()                                  |
    | helper(arr, res, i+1, slate);                |
    |      +-------------------------------------+ |
    |      | i = 1                               | |
    |      | ....                                | |
    |      | slate.push(char)                    | |
    |      | helper(arr, res, i+1, slate);       | |
    |      |      +----------------------------+ | |
    |      |      | i = 2                      | | |
    |      |      |  ...                       | | |
    |      |      | res.push(slate.join(''));  | | |
    |      |      | return;                    | | |
    |      |      +----------------------------+ | |
    |      | // i is still 1                     | |
    |      | slate.pop()                         | |
    |      | helper(arr, res, i+1, slate);       | |
    |      |      +----------------------------+ | |
    |      |      | i = 2                      | | |
    |      |      |  ...                       | | |
    |      |      | res.push(slate.join(''));  | | |
    |      |      | return;                    | | |
    |      |      +----------------------------+ | |
    |      | // i is still 1                     | |
    |      +-------------------------------------+ |
    | // i is still 0                              |
    +----------------------------------------------+

So we see that, in this particular algorithm, the size of the call stack (i.e. the depth of the recursion tree) corresponds exactly to the value of the variable i in the current execution context. When a function returns, the size of the call stack is reduced (i.e. the recursion depth decreased), and so we arrive in a state (popped from the stack) where there is another instance of i that also has a value that matches the now current size of the call stack.