如何将同步和异步递归函数转换为JavaScript中的迭代

Question

寻找同步和异步递归函数的特定实现,这些函数可以用作将未来递归函数转换为平面迭代的起点.

以下是递归函数的两个示例:同步和异步.

我正在寻找的是使用没有递归的堆栈的实现.

例如,它可能会像这样工作:

var output = syncStack(myRecursiveFunctionTurnedIterative, [])

或者,如果那是不可能的,那么只需使用堆栈重新实现下面的两个函数,这应该是一个足够好的开始.例如

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
    }
  }
}

这个问题的原因是,多年来我一直在努力学习如何做到这一点,但从未找到过(a)容易记住如何做的系统,以及(b)实用的系统.

同步

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
    }
  }
}

台异步

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()
}

例如,这可能会开始看起来像:

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)
  }
}

但那就是我迷路的地方.不知道如何传递堆栈以及如何设置功能.

想知道如何在实践中将它们写为非递归函数.我已经看到了从递归到迭代的方式,但它们都非常理论化.

Answer 1

为了让我们使用调用另一个函数的函数转换一个过程(无论它是否是相同的函数,也就是'递归',没有区别),我们需要将它分离到之前发生的过程中.呼叫和呼叫后的任何程序.如果在out-call之后没有过程,并且out-call是相同的函数,我们可以将其描述为"tail recursive",它可以使迭代转换更简单,只需将调用参数推送到堆栈(例子).实际上,将尾递归转换为迭代堆栈过程有助于我在多个实例中克服浏览器的递归深度限制.

转换为尾递归

为了将递归转换为尾递归,我们必须考虑如何处理从递归调用传递的信息,以及我们是否可以转换此过程以利用递归本身中的参数.因为在您的特定示例中,out-call结果发生的唯一事情是局部变量的设置output,并且output是一个对象,在JavaScript中通过引用传递,我们可以进行此转换.所以这是一个简单的重构,它将使我们能够使用一个简洁的堆栈(我跳过了尾递归代码到堆栈实现;留下作为读者的练习):

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
    }
  }
}

概括堆栈和订购操作

由于将递归转换为尾递归并不总是容易和直接的,让我们考虑如何使用堆栈以类似于原始递归的方式迭代地对操作进行排序.我们还会稍微概括一下我们的堆栈,这将有助于我们使用您的第二个"异步"示例.让我们存储要调用的函数以及参数,而不仅仅是调用参数.就像是:

(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]
]

我们知道,一个堆栈操作"后进先出",这意味着如果我们有一个外调用另一个函数后续操作的功能,这些后续操作将需要被压入堆栈之前的外呼这样从堆栈处理的顺序将是这样的:

(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)

(所有这些都是利用堆栈概念来命令我们的操作.如果你想获得真正的幻想(甚至更复杂),将每条指令编码为一个函数并模拟一个实际的调用堆栈,具有暂停主程序中的下一条指令,因为对其他函数的调用被推送到它.)

现在让我们将这个想法应用到您的示例中:

同步示例

我们不仅在这里有呼出后程序,而且我们有一个完整的for循环这样的调用.(请注意,直接在代码段查看器中查看的控制台日志不完整.请查看浏览器的JS控制台以获取完整的日志.)

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());

同步的例子

(我冒昧地next()在最后加了一个电话asynca,我想你忘记了.)

在这里,除了多个交织函数调用之外,我们还有一个复杂的问题,即调用是异步的,这基本上意味着将有多个堆栈进程.因为在这个特定的例子中,堆栈进程不会在时间上重叠,所以我们只使用一个堆栈,顺序调用.(请注意,直接在代码段查看器中查看的控制台日志不完整.请查看浏览器的JS控制台以获取完整的日志.)

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());

调用堆栈仿真

我不确定我是否有时间去做这个,但这里有一些通用模板的想法.将其他函数调用为相关较小函数以实现暂停执行的单独函数,可能将它们编码为具有操作数组和键以模拟局部变量的对象.

然后编写一个控制器和接口,可以区分对另一个函数的调用(类似编码,如果它也有out-calls),将"函数"的对象(或堆栈框架)推入堆栈,记住下一个函数的位置在线指导.有许多创造性的方法可以通过JavaScript实现,使用对象键作为被调用函数的"返回地址",例如,可以使控制器知道.

正如其他人在此处所指出的那样,每个函数调用另一个函数都会将其转换为迭代序列.但是可能有许多功能可以适用于这样的方案,并且允许我们从执行限制和排序的附加控制中受益.