How to convert sync and async recursive function to iteration in JavaScript
In order for us to convert a procedure with a function that calls out to another function (whether or not it's the same function, aka 'recursive', makes no difference), we will need to separate it into the procedure that occurs before such a call and any procedures subsequent to the call. If there are no procedures after the out-call and the out-call is to the same function, we can describe it as "tail recursive," which can make the conversion to iterative much much simpler, simply pushing the call parameters to the stack (Example). In fact, converting tail-recursion to an iterative stack process has helped me overcome browsers' recursion-depth limits in more than one real instance.
Converting to tail-recursive
In order to convert a recursion to tail-recursive, we must consider how the information delivered from the recursive call is processed and whether we can transform this process to utilize parameters in the recursion itself. Since in your particular example, the only thing that happens with the out-call result is the setting of the local variable, output, and output is an object, which in JavaScript is passed by reference, we are in a position to make this transformation. So here's a simple refactor that will enable us to use a succinct stack (I skipped over the tail-recursive code to the stack implementation; left as an exercise for the reader):
var references = {}var object = { a: { b: { c: { d: { e: 10, f: 11, g: 12 } } } }}object.a.b.c.d.x = objectobject.a.b.c.d.y = object.a.bvar id = 1//var x = circularReferences(object, references)//console.log(x)//function circularReferences(object, references) {// => add parameters, 'output' and 'key'var stack = [[object, references, null, null]];while (stack.length){ [_object, _references, _callerOutput, _key] = stack.pop() var output = {} if (_object.__circularid__){ _callerOutput[_key] = '[Circular]' // Log our example console.log('OUTPUT VALUE: ' + JSON.stringify(_callerOutput)) // Exit continue; } Object.defineProperty(_object, '__circularid__', { value: id++ }) for (var key in _object) { var value = _object[key] if (value && typeof value == 'object') { console.log(value) //var is = circularReferences(value, references) // if (is) output[key] = '[Circular]' stack.push([value, _references, output, key]) } else { output[key] = value } }}Generalizing the stack and ordering operations
Since it may not always be easy and straightforward to transform a recursion to tail-recursive, let's consider how we can use the stack to order operations iteratively in a way similar to the original recursion. We'll also generalize our stack a bit, which will help us with your second, "Asynchronous," example. Rather than only the call parameters, let's store both which function to call as well as the parameters. Something like:
(stack) [ [function A, parameters for this call of A, additional refs for this call of A], [function B, parameters for this call of B, additional refs for this call of B]]As we know, a stack operates "last in, first out," which means if we have a function with operations subsequent to an out-call to another function, those subsequent operations will need to be pushed to the stack before the out-call so that the order of processing from the stack will be something like:
(stack) [first_call]pop stack => first_call: process procedure before out_call push procedure after out_call => (stack) [procedure after out_call] push out_call => (stack) [procedure after out_call, out_call]pop stack => out_call (maybe followed by a whole other series of stack interactions)pop stack => procedure after out_call (maybe use stored result)(All of this is a bit of a hack to utilize the stack concept to order our operations. If you want to get real fancy (and even more complicated), code each instruction as a function and simulate an actual call stack with the ability to pause the next instruction in the main program as calls to other functions are pushed to it.)
Now let's apply this idea to your examples:
Synchronous example
Not only do we have after-out-call procedures here, but we have an entire for-loop with such calls. (Please note that the console logs viewed directly in the snippet viewer are incomplete. Observe your browser's JS console for the complete logs.)
var references = {};var object = { a: { b: { c: { d: { e: 10, f: 11, g: 12 } } } }};object.a.b.c.d.x = object;object.a.b.c.d.y = object.a.b;var id = 1;let iterativeProcess = { stack: [], currentResult: undefined, start: function(){ // Garbage collector :) iterativeProcess.currentResult = undefined console.log('Starting stack process') // Used for debugging, to avoid an infinite loop let keep_going = 100; while (iterativeProcess.stack.length && keep_going--){ let [func_name, func, params, refs] = iterativeProcess.stack.pop(); console.log('\npopped: [' + func_name + ', ' + params + ', ' + JSON.stringify(refs) + ']'); params.unshift(refs); func.apply(func, params); } return 'Stack process done\n\n'; }};let circularReferences = { preOutCall: function(refs, _object, _references){ var output = {}; if (_object.__circularid__){ console.log('preOutCall: _object has __circularid__ setting currentResult true') iterativeProcess.currentResult = true; // Exit return; } Object.defineProperty(_object, '__circularid__', { value: id++ }) // Push post-out-call-procedure to stack console.log('Pushing to stack postOutCall ' + Object.keys(_object)[0]) iterativeProcess.stack.push(['postOutCall', circularReferences.postOutCall, [], output]); // Call for-loop in reverse let keys = Object.keys(_object); for (let i=keys.length-1; i >=0; i--) circularReferences.subroutineA(output, _object, keys[i], _references); }, subroutineA: function(refs, _object, key, _references){ var value = _object[key]; if (value && typeof value == 'object'){ console.log('subroutineA: key: ' + key + '; value is an object: ' + value); console.log('Pushing to stack postSubroutineA ' + key) iterativeProcess.stack.push(['postSubroutineA', circularReferences.postSubroutineA, [key], refs]); // Push out-call to stack console.log('Pushing to stack preOutCall-' + key) iterativeProcess.stack.push(['preOutCall-' + key, circularReferences.preOutCall, [value, _references], refs]); } else { console.log('subroutineA: key: ' + key + '; value is not an object: ' + value); console.log('Pushing to stack subroutineA1 ' + key) iterativeProcess.stack.push(['subroutineA1', circularReferences.subroutineA1, [key, value], refs]); } }, subroutineA1: function(refs, key, value){ console.log('subroutineA1: setting key ' + key + ' to ' + value); refs[key] = value; }, postSubroutineA: function(refs, key){ let is = iterativeProcess.currentResult; //circularReferences(value, _references) if (is){ refs[key] = '[Circular]'; console.log('postSubroutineA: Object key: ' + key + ' is circular; output: ' + JSON.stringify(refs)); } else { console.log('postSubroutineA: key: ' + key + '; currentResult: ' + iterativeProcess.currentResult + '; output: ' + JSON.stringify(refs)); } }, postOutCall: function(){ // There is no return statement in the original function // so we'll set current result to undefined iterativeProcess.currentResult = undefined; }};// Convert the recursive call to iterative//var x = circularReferences(object, references)//console.log(x)console.log('Pushing to stack')iterativeProcess.stack.push(['preOutCall', circularReferences.preOutCall, [object, references]]);console.log(iterativeProcess.start());Asychronous example
(I took the liberty to add a call to next() at the end of asynca, which I think you forgot.)
Here, in addition to multiple, interweaving function calls, we have the complication that calls are asynchronous, which basically means there will be more than one stack process. Since in this particular example stack-processes won't overlap in time, we'll just use one stack, called sequentially. (Please note that the console logs viewed directly in the snippet viewer are incomplete. Observe your browser's JS console for the complete logs.)
let async = { asynca: function(refs, items, callback){ let i = 0; function next(refs){ console.log('next: i: ' + i); let item = items[i++]; if (!item){ console.log('Item undefined, pushing to stack: callback'); iterativeProcess.stack.push(['callback', callback, [], refs]); } else { console.log('Item defined, pushing to stack: item'); iterativeProcess.stack.push(['item', item, [next], refs]); } } console.log('asynca: pushing to stack: next'); iterativeProcess.stack.push(['next', next, [], refs]); }, async1a: function(refs, callback) { // Some stuff... setTimeout(function(){ if (true) { var items = [ async.async2a, // ... ] console.log('async1a: pushing to stack: asynca'); iterativeProcess.stack.push(['asynca', async.asynca, [items, callback], refs]); } else { console.log('async1a: pushing to stack: callback'); iterativeProcess.stack.push(['callback', callback, [null, true], refs]); } // Since there was a timeout, we have to restart the stack process to simulate // another thread iterativeProcess.start(); }, 200) }, async1b: function(refs, callback) { // Some stuff... setTimeout(function(){ if (true) { var items = [ async.async2a, // ... ] console.log('async1b: pushing to stack: asynca'); iterativeProcess.stack.push(['asynca', async.asynca, [items, callback], refs]); } else { console.log('async1b: pushing to stack: callback'); iterativeProcess.stack.push(['callback', callback, [null, true], refs]) } // Since there was a timeout, we have to restart the stack process to simulate // another thread console.log(iterativeProcess.start()); }, 200) }, async1c: function(refs, callback) { // Some stuff... setTimeout(function(){ if (true) { var items = [ async.async2a, // ... ] console.log('async1c: pushing to stack: asynca'); iterativeProcess.stack.push(['asynca', async.asynca, [items, callback], refs]); } else { console.log('async1c: pushing to stack: callback'); iterativeProcess.stack.push(['callback', callback, [null, true], refs]); } // Since there was a timeout, we have to restart the stack process to simulate // another thread console.log(iterativeProcess.start()); }, 200) }, async2a: function(refs, callback) { console.log('async2a: pushing to stack: callback'); iterativeProcess.stack.push(['callback', callback, [], refs]); }}let iterativeProcess = { stack: [], currentResult: undefined, start: function(){ // Garbage collector :) iterativeProcess.currentResult = undefined console.log('Starting stack process') // Used for debugging, to avoid an infinite loop let keep_going = 100; while (iterativeProcess.stack.length && keep_going--){ let [func_name, func, params, refs] = iterativeProcess.stack.pop(); console.log('\npopped: [' + func_name + ', [' + params.map(x => typeof x) + '], ' + JSON.stringify(refs) + ']'); params.unshift(refs); func.apply(func, params); } return 'Stack process done\n\n'; }};let _items = [ async.async1a, async.async1b, async.async1c // ...];console.log('Pushing to stack: asynca');iterativeProcess.stack.push(['asynca', async.asynca, [_items, function(){console.log('\ndone')}]]);console.log(iterativeProcess.start());Call stack emulation
I'm not sure if I'll have time to get to this but here are some ideas for a general template. Separate functions that call other functions into relevant smaller functions to enable a pause in execution, perhaps code them as an object with an array of operations and keys to simulate local variables.
Then write a controller and interface that can distinguish a call to another function (similarly coded if it also has out-calls), push that "function"'s object (or stack-frame) onto the stack, remembering the place of the next instruction in line. There are many creative ways this can be accomplished with JavaScript, using object keys for the "return address" of the called function, for example, that the controller can be made aware of.
As others have noted here, each function with a call to another function presents its own challenge to convert it to an iterative sequence. But there may be many functions that could be amenable to such a scheme, and allow us to benefit from the added control of execution limits and sequencing.
I think it's a bad idea. I see benefit in this as purely an intellectual exercise, but you're forcing a very messy and complicated answer to a simple resource problem that could be solve by other means.
When a function in Javascript executes, it pushes a return address, function parameters, and local variables onto a stack. It's virtually impossible to get much savings on these with a naturally-recursive problem of indefinite depth by forcing it into a loop. A previous response (whose name I cannot type or even copy-paste well since it's in an RTL enconding) discussed tail recursion, and if you can fit the pattern you can get some slight savings of not pushing the return address onto the stack, but Javascript engines might be able to take care of that for you anyhow.
One difference and extra performance load compared to other languages, for example PHP, would be that Javascript also creates a closure for each invocation of the function. This could be trivial or substantial resource cost in very deep, very wide datasets, the type likely to actually cause a problem where one might think non-recursion would solve that problem. There is a means to invoke a function without a closure, however, by using the Function constructor. We shy away from these because eval-is-evil and they do take an extra step to compile, but once created, this might reduce any extra overhead from closures in deep recursion. The live compile performance hit should be more than compensated by reduced overhead in deep recursion calls.
Other performance drags can be creating an arguments object and execution context (this). We also now have arrow functions which will simply inherit the outer scope's instances. So the actual recursive portion should be an arrow function. If it needs a this, pass it by the outer Function's closure, or pass it as a parameter.
Here's a general map:
const outerFunction=new Function( 'arg1,arg2,arg3', ` // Initialize and create items that simply must be transferred by closure ... const recursiveFunction=(param1,param2,param3)=>{ ... const value=recursiveFunction(newParam1,newParam2,newParam3) ... } return recursiveFunction(firstParam1,firstParam2,firstParam3) `)Once into the general pattern, optimize the inner loop as much as possible. Don't build and recombine objects and arrays if the originals can be passed as references. Don't do any duckchecking or extraneous processing in the recursive portion. Javascript programmers aren't taught much about memory leaks, as the language has traditionally been short snippets that get wiped when the page is refreshed, so learn to spot instances where items no longer needed can't be garbage collected, and for that matter reduce items that need to be garbage collected if the problem is speed instead of memory. Remember that all primitives are immutable, and old values will be subject to being GC'd when assigned new values. Consider using Typed Arrays where sensible, to prevent this.
Even if this doesn't solve the OP's concerns, I hope this approach could be helpful to others who find this question on Google.
Let's just define a simple function, along with our parameters.
function syncLoop(iterations, process, exit){ // Body of the function}Just to talk about the params real quick;
iterations = the number of iterations to carry outprocess = the code/function we're running for every iterationexit = an optional callback to carry out once the loop has completedSo we have our function shell, now we need to instantiate an index, and a boolean to keep track of if we're done looping or not.
function syncLoop(iterations, process, exit){ var index = 0, done = false; // Body of function}Now we can keep track of where we are, and if we're finished or not (both important in loops!). The done boolean is going to be our way to check if we want to actually run again when called.
Right, this is where it gets slightly more complicated. We're going to create an object loop which is actually our loop object, and we're going to return it so we can control the loop from outside the function.
function syncLoop(iterations, process, exit){ var index = 0, done = false; var loop = { // Loop structure }; return loop;}I'll come back to this is a little while. Ok, so we have our loop. What's important to have in a loop? Well, we need a way to access the index, move on in the loop, and a way to kill the loop - so let's implement these methods.
function syncLoop(iterations, process, exit){ var index = 0, done = false, shouldExit = false; var loop = { next:function(){ if(done){ if(shouldExit && exit){ return exit(); // Exit if we're done } } // If we're not finished if(index < iterations){ index++; // Increment our index process(loop); // Run our process, pass in the loop // Otherwise we're done } else { done = true; // Make sure we say we're done if(exit) exit(); // Call the callback on exit } }, iteration:function(){ return index - 1; // Return the loop number we're on }, break:function(end){ done = true; // End the loop shouldExit = end; // Passing end as true means we still call the exit callback } }; return loop;}Ok, to talk through this a little bit;
The loop.next() is our loop controller. Our process should call loop.next() when it wishes to complete an iteration and move to the next. Basically, all loop.next() does is call our desired process again, unless we're finished, in which case it calls the final callback.
The loop.iteration() function simply returns the index we're on. The first initialization means we'll always be one index ahead of the current iteration, so we return index - 1.
The loop.break() just tells the loop to finish on the current iteration. You can pass an optional value to tell the loop to end as normal and call the exit() callback if desired. This is useful for loops which need to cleanup after themselves.
Right, we have a majority of the body here. So let's just kick it off, by calling loop.next() just before we return our loop.
function syncLoop(iterations, process, exit){ var index = 0, done = false, shouldExit = false; var loop = { next:function(){ if(done){ if(shouldExit && exit){ return exit(); // Exit if we're done } } // If we're not finished if(index < iterations){ index++; // Increment our index process(loop); // Run our process, pass in the loop // Otherwise we're done } else { done = true; // Make sure we say we're done if(exit) exit(); // Call the callback on exit } }, iteration:function(){ return index - 1; // Return the loop number we're on }, break:function(end){ done = true; // End the loop shouldExit = end; // Passing end as true means we still call the exit callback } }; loop.next(); return loop;}And we're done! All that matters now is implementing our loop and running it, so let's see an example;
syncLoop(5, function(loop){ setTimeout(function(){ var i = loop.iteration(); console.log(i); loop.next(); }, 5000);}, function(){ console.log('done');});The above code simply prints out the current iteration we're with 5 seconds between each print, then logs done when complete. Go ahead and try it inside your browser console. Let's also check that our loop.break() works as expected.
var myLoop = syncLoop(5, function(loop){ setTimeout(function(){ var i = loop.iteration(); console.log(i); loop.next(); }, 5000);}, function(){ console.log('done');});setTimeout(myLoop.break, 10000);In this scenario, we should see only the first two iterations printed before the loop is ended. Because we aren't passing a boolean value to myLoop.break() it's not logging out done. We could change this by using the following:
setTimeout(function(){ myLoop.break(true);}, 10000);One important thing to note is that you can't kill a loop (cleanly) whilst in mid execution, it will wait until the current iteration is complete (which actually makes a lot of sense). It will just queue the break for the start of the next iteration, which is checked in loop.next().