CODEWITHSUNDEEP
javascriptalgorithmrecursion
hoi
hoi

Reputation: 1

I have a question about how the function works

While solving the algorithm, there is a part that I do not understand about how the function works.

function letterCombinations(digits) {
    var map = ['0', '1', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    var res = [];
    var prefix = [];

    if (digits.length) {
        traverse(0);
    }
    return res;

    function traverse(idx) {
        if (idx === digits.length) {
            return res.push(prefix.join(''));
        }

        var str = map[digits[idx] - '0'];

        for (var i = 0; i < str.length; i++) {
            prefix.push(str[i]);
            traverse(idx + 1);
            prefix.pop();
        }
    }
}

When the conditional statement inside the traverse function is encountered

 if (idx === digits.length) {
        return res.push(prefix.join(''));
    }

Why is the pop method executed without exiting the function?

prefix.pop()

Upvotes: 0

Views: 54

Answers (2)

hackape
hackape

Reputation: 19957

You wording is kinda ambiguous, but I think get what you're really asking.

The prefix.pop() is a line inside traverse() function, and the traverse() recursively calls itself.

Take for example letterCombinations('23') where corresponding str would be 2: 'abc', 3: 'def'. The process can be visualized as following pseudo code:

traverse(0)
  i=0, push('a') // prefix=['a']

  traverse(1)
    loop when i=0:
      push('d')       // prefix=['a', 'd']
      traverse(2)     // since `2==digits.length`, it's a short-circuit return
                      // no `pop()` called inside `traverse(2)`
      pop_1() -> 'd'  // prefix=['a']
    
    loop when i=1:
      push('e')       // prefix=['a', 'e']
      traverse(2)     // short-circuit return
      pop_1() -> 'e'  // prefix=['a']

    loop when i=3:
      ...
    
  pop_0()

You get confused because you're fixing your eye on the prefix.pop() line of code in traverse(0), marked as pop_0() in the pseudo code. But you forget to trace the recursion.

Use your imagination and step into traverse(1), you'll find another prefix.pop() call there, marked as pop_1().

So to answer your question:

Why is the pop method executed without exiting the function?

You're right about the fact that, we haven't exit traverse(0) yet, but the pop method is actually called inside traverse(1). Out there, we've exit traverse(2) because of the short-circuit return.

Upvotes: 1

k.s.
k.s.

Reputation: 3004

The .pop() method has nothing to do with the function it's being called in. That method is part of the array object, see docs

The pop() method removes the last element from an array and returns that element. This method changes the length of the array.

The return statement actually exists the function. So if you want when .pop() is called, the function to be exited write:

return prefix.pop();

Or if you want the current iteration of the loop finished, you can call continue

Upvotes: 0

Related Questions