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?

Because i is a local variable and each new execution of helper will have its own version of i, which can have a different value. When a recursive call returns, and the calling code continues, then its own i is relevant (again). — trincot
– trincot, Commented Mar 7, 2021 at 20:32
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? — Heymanyoulookkindacool
– Heymanyoulookkindacool, Commented Mar 7, 2021 at 20:36
Why would you expect the recursive call to change i? It never does. If you look at the code, you see that there is no assignment to i ever in helper. The only thing that happens is that i+1 is passed on to the recursive call, where it will become the initial and only value of the local variable i that only lives in that recursive execution context. When that execution terminates, we're back at the caller, where there is still the unchanged i living there. — trincot
– trincot, Commented Mar 7, 2021 at 20:51
Could you use an example for this? So in this case, after the first function calls returns, i stops at 5. Then what happens next? Would 1 now be added to i to make it 6? — Heymanyoulookkindacool
– Heymanyoulookkindacool, Commented Mar 7, 2021 at 21:06

trincot · Accepted Answer · 2021-03-07 21:32:00Z

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.

Thank you. This is clearer. However, may I ask why it is that there needs to be 2 recursion calls for the call stack to be established? If we only have 1 recursion call, it will be like an iterative problem.
Indeed, it depends on the problem that an algorithm is solving. In some cases you need multiple recursive calls, and in other cases you only need one. When there is only one, then sometimes the principle of tail recursion can be applied, and the algorithm can be rewritten in an iterative way. For this particular problem that your code solves, there is also an iterative way to achieve the result. But that goes beyond the scope of your question.

Scott Sauyet · Accepted Answer · 2021-03-08 14:00:04Z

Trincot gave a helpful detailed response on how that function works internally. I'd just like to point out a significant simplification you could write:

const getSpellableWords = ([x, ...xs]) => x == undefined ? [''] : ((ps = getSpellableWords (xs)) => [...ps .map (p => x + p), ...ps]) () console .log ( getSpellableWords (['A', 'T', 'C', 'K']) )

.as-console-wrapper {max-height: 100% !important; top: 0}

Here we note that the words we can make either include the first character or they don't. We can recursively calculate all the words from the remainder and then return the result of combining that array of words with those ones found by prepending the first character to each. And of course our recursion bottoms out if there are no characters left, in which our array returned contains only the empty string.

There is a slight bit of syntactic trickery here, with an IIFE in the recursive branch. We might prefer to use a call helper function, which takes a function and any arguments and calls that function with those arguments. Sometimes that's clearer:

const call = (fn, ...args) => fn (...args) const getSpellableWords = ([x, ...xs]) => x == undefined ? [''] : call ( (ps) => [...ps .map (p => x + p), ...ps], getSpellableWords (xs) )

Thank you for your answer. Just wanted to ask that, even though it is more clean, I think it's pretty hard to understand looking at the code. Is this style of programming usually something that used often in production?
@Heymanyoulookkindacool: That's a matter of preference and of experience. I find this much easier to read and to reason about than the code in the question. I've encouraged my teams to move toward this style, so I know that it's in production in at least one large company. ;-)

Collectives™ on Stack Overflow

When does the call stack get set up in Javascript?

2 Answers 2

4 Comments

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

2 Comments

Linked

Related