Recursion and Loops - Maximum Call Stack Exceeded

0
votes

I'm trying to build a function that adds up all the numbers within a string... for example, 'dlsjf3diw62' would end up being 65.

I tried to be clever and put together a recursive function:

function NumberAddition(str) { 
  var numbers='1234567890';
  var check=[];
  str=str.split[''];
  function recursive(str,check) {
    if (str.length==0)
      return check;
    else if (numbers.indexOf(str[0])>=0)
    {
      for (i=0;i<str.length;i++){
        if (numbers.indexOf(str[i])<0)
          check.push(str.slice(0,i));
        str=str.slice(i);
        return recursive(str,check);
      }
    }
    else
      str.shift();
    return recursive(str,check);
  }

You'll see that I'm trying to get my numbers returned as an array in the array named check. Unfortunately, I have a maximum call stack size exceeded, and I'm not sure why! The recursion does have a base case!! It ends once str no longer has any contents. Why wouldn't this work? Is there something I'm missing?

-Will

2
javascriptrecursion
Learn to use your browser's developer tools and step through your code. Also, there would be a far easier way of achieving what you're trying. - Lee Taylor
The code you posted seems to be missing something; it's hard to tell where the function ends, and in particular something looks wrong with the last few lines. There's a missing curly brace. - Pointy
What is the far easier way? - user3546595
@user3546595 strip out the numeric substrings with a regular expression and then reduce the result. - Pointy
Sorry, I didn't copy and paste to the last line. It's really the function named'Recursive' that isn't working. - user3546595

2 Answers

2
votes

You can achieve the same thing with a far easier solution, using regular expressions, as follows:

var str = 'dlsjf3diw62';
var check = str.match(/\d+/g); // this pattern matches all instances of 1 or more digits

Then, to sum the numbers, you can do this:

var checkSum = 0;
for (var i = 0; i < check.length; i++) {
    checkSum += parseInt(check[i]);
}

Or, slightly more compact:

var checkSum = check.reduce(function(sum, num){ return sum + parseInt(num) }, 0);
1
votes

The reason your recursion doesn't work is the case where you do enter the for loop, because you've found a digit, but the digits continue to the end of the string. If that happens, the return inside the for loop never happens, and the loop ends. After that, the .shift() does not happen, because it's in that else branch, so you return re-process the same string.

You shouldn't solve this particular problem that way, but the code makes a good example of the anti-pattern of having return statements inside if bodies followed by else. Your code would be clearer (and would work) if it looked like this:

function recursive(str, check) {
    if (str.length == 0)
        return check;

    if (numbers.indexOf(str[0]) >= 0) {
        // Find the end of the string of digits, or
        // the end of the whole thing
        for (var i = 0; i < str.length && numbers.indexOf(str[i]) >= 0; i++);

        check.push(str.slice(0, i));
        str = str.slice(i);
        return recursive(str, check);
    }

    // A non-digit character
    str.shift();
    return recursive(str, check);
}

In that version, there are no else clauses, because the two if clauses always involve a return. The for loop is changed to simply find the right value of "i" for the subsequent slicing.

edit — one thing this doesn't fix is the fact that you're pushing arrays into your "check" list. That is, the substring "62" would be pushed as the array ["6", "2"]. That's not a huge problem; it's solved with the addition of a .join() in the right place.