In my previous post I showed a technique to prevent overfilling the stack in deep recursion cases. In my example there I was using this technique for a recursive function that has no additional action to perform after the recursive call returns (that is, the case that would be optimized by Tail Calls if JavaScript implemented them). In this post we'll see how to apply this technique for recursive functions that perform additional actions after the child recursive call.
Let's say we have this recursive function:
function transformString (source){
if (source.length === 1)
return source.toUpperCase() + source;
let curItem = source[0];
let transformed = transformString(source.substring(1));
return curItem.toUpperCase() + transformed + curItem;
}
let st = "helloworld";
console.log(transformString(st));
//Output:
//HELLOWORLDdlrowolleh
As you can see, after invoking the recursive function we still run an action with the returned value and a value obtained before invoking the recursion (curItem). When applying the technique of the previous post we no longer have the current stack frame for running this action (as we are no longer stacking stack frames), so we have to provide this "post action" to the recursive function. So basically, the adapted recursive function receives an array with all the post actions. Notice that these "post action" functions trap as closure variables the values that normally would be in their stack frames.
//postActions: array of functions where we stack the code to run after recursion ends
//resFn: Promise resolve function
function transformStringWithTimeout (source, counter = 0, postActions, resFn){
let curItem;
let postAction = transformed => curItem.toUpperCase() + transformed + curItem;
//initial call
if (resFn === undefined){
var pr = new Promise((res, rej) => resFn = res);
postActions = [];
}
//end recursion
if (source.length === 1){
let initValue = source.toUpperCase() + source;
//using reduceRight to run the stack of actions
let result = postActions.reduceRight((accum, fn) => fn(accum), initValue);
resFn(result);
}
else{
curItem = source[0];
postActions.push(postAction);
//use this so low "recursion break" value for the sake of testing
if (counter < 5){
transformStringWithTimeout(source.substring(1), ++counter, postActions, resFn);
}
else{
//let's release the stack
setTimeout(() => {
console.log("timeout handling");
transformStringWithTimeout(source.substring(1), 0, postActions, resFn);
}, 0);
}
}
return pr;
}
(async () => {
console.log("-- with timeout");
let result = await transformStringWithTimeout("helloworld");
console.log(result);
})();
//Output:
//HELLOWORLDdlrowolleh
//-- with timeout
//timeout handling
//HELLOWORLDdlrowolleh
As you see, I've moved into a function postAction the piece of code that in the original function we were running after the recursive call. I push those postActions in an array postActions that I keep passing over in ensuing calls. When we reach the end of the recursion we run these post actions in reverse order. Notice than rather than using a for-of and pop for executing these actions I'm using reduceRight, just for the pleasure of it :-)
You can get the full code here
