How to convert sync and async recursive function to iteration in JavaScript

Question

Looking for a specific implementation for both sync and async recursive functions that could be used as a starting point to turn future recursive functions into flat iteration.

Below are two examples of recursive functions: Synchronous and Asynchronous.

What I am looking for is an implementation of both using a stack without recursion.

For example, maybe it would work like this:

var output = syncStack(myRecursiveFunctionTurnedIterative, []) 

Or if that's not possible, then just a reimplementation of the two functions below using a stack, and that should be a good enough start. E.g.

var stack = []  function circularReferences(object, references, stack) {   var output = {}   if (object.__circularid__) return true   Object.defineProperty(object, '__circularid__', { value: id++ })   for (var key in object) {     var value = object[key]     if (value && typeof value == 'object') {       console.log(value)       stack.push(???)       circularReferences()       stack.pop()       if (is) output[key] = '[Circular]'     } else {       output[key] = value     }   } } 

The reason for this question is, I have tried over the years to learn how to do this, but have never found a system that is (a) easy to remember how to do, and (b) practical.

Synchronous

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    var x = circularReferences(object, references)  console.log(x)    function circularReferences(object, references) {    var output = {}    if (object.__circularid__) return true    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]'      } else {        output[key] = value      }    }  }

Asychronous

var items = [    async1a,    async1b,    async1c    // ...  ]    asynca(items, function(){    console.log('done')  })    function asynca(items, callback) {    var i = 0      function next() {      var item = items[i++]      if (!item) return callback()        item(next)    }  }    function async1a(callback) {    // Some stuff...    setTimeout(function(){      if (true) {        var items = [          async2a,          // ...        ]          asynca(items, callback)      } else {        callback(null, true)      }    }, 200)  }    function async1b(callback) {    // Some stuff...    setTimeout(function(){      if (true) {        var items = [          async2a,          // ...        ]          asynca(items, callback)      } else {        callback(null, true)      }    }, 200)  }    function async1c(callback) {    // Some stuff...    setTimeout(function(){      if (true) {        var items = [          async2a,          // ...        ]          asynca(items, callback)      } else {        callback(null, true)      }    }, 200)  }    function async2a(callback) {    return callback()  }

For example, that may start looking something like:

var items = [   async1a,   async1b,   async1c   // ... ]  asynca(items, function(){   console.log('done') }, [])  function asynca(items, callback, stack) {   var i = 0    function next() {     var item = items[i++]     if (!item) return callback()     stack.push(item)   } } 

But that's where I get lost. Not sure how to pass around the stack and how the functions should be setup in general.

Wondering how to in practice write those as non-recursive functions. I've seen Way to go from recursion to iteration but they are all very theoretical.

Answer 1

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 = object  object.a.b.c.d.y = object.a.b    var 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.