Tail call optimization

The Error

uncaughtException Maximum call stack size exceeded

This is specifically for nodejs RECURSIVE functions. When you know your recursive function is completing (you can use a smaller dataset and it works perfectly), and you receive a call stack size exceeded error when running a full dataset.

The Solution

The quick fix is to set the stack size higher when you start node, however this doesn’t fix the root of the problem.

node --stack-size=1200 index.js

Note that the 1200 is in kB, and the default is about 1MB.

The Solution 2 (Tail Call Optimization)

Not really sure what it is, I just did a lot of googling. Here are the main points and how I fixed my function since it’s hard to find online.

// stripped down function - not even sure if it works
// should split these camel cased words into single words 
// DomainEndpointOptions => domain endpoint options
// EnforceHTTPS => enforce https
// RDSService => rds service
// azureTest => azure test
// ADHybridHealthServiceExtra LongVPC => ad hybrid health service extra long vpc
//
// this is not using Tail Call optimization 
function recursiveFunctionBad(str){
    if(!str){
        return [];
    }
    if(str.match(/(^[A-Z0-9]+$|^[A-Z][a-z0-9]+$|^[a-z0-9]+$)/)){
  	return [str];
    }
    if(str.match(/[a-z][A-Z]{1}$/)){
  	return [str];
    }
    let results = [];
    str = str.replace(/([A-Z][a-z0-9]+|[A-Z]+|[a-z0-9]+)([A-Z][A-z0-9]+)/g, '$1,$2');
    str.split(',').forEach(row => {
        results = [...results, ...recursiveFunctionBad(row)];
    });

    return results;
}


// the fixed function
// call with an empty 2nd argument
// recursiveFunctionFixed('some string', [])
function recursiveFunctionFixed(str, results){
    if(!str){
        return results;
    }
    if(str.match(/(^[A-Z0-9]+$|^[A-Z][a-z0-9]+$|^[a-z0-9]+$)/)){
  		return [...results, str];
    }
    if(str.match(/[a-z][A-Z]{1}$/)){
  		return [...results, str];
    }

    str = str.replace(/([A-Z][a-z0-9]+|[A-Z]+|[a-z0-9]+)([A-Z][A-z0-9]+)/, '$1,$2');
	  let substr = str.split(',')[0];
    str = str.split(',')[1];

    return recursiveFunctionFixed(str, results);
}

So my understanding is you must remove “waiting for the response” inside the recursive function. All the “waiting” must be done in the return line. For recursiveFunctionFixed():

  1. I moved the results to be a part of the function arguments.
  2. Removed the results array from being created inside each call.
  3. Removed the forEach loop.
  4. Changed the stop recursion logic.

If done correctly, the call stack will not need to persisted through each recursion.

Share this:

Leave a comment

16 − eleven =