寻找同步和异步递归函数的特定实现，可以将其用作将来将递归函数转换为平面迭代的起点。
以下是两个递归函数示例:同步和异步。
我正在寻找的是使用堆栈而不递归的实现。
例如，也许它将像这样工作:
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)
}
}
但这就是我迷路的地方。不确定如何传递堆栈和如何在常规中设置功能。
想知道如何在实践中将其编写为非递归函数。我看过Way to go from recursion to iteration，但它们都是非常理论性的。
最佳答案
为了使我们可以将带有调用一个函数的函数的过程转换为另一个函数(无论是否是同一个函数，又称为“递归”，都没有区别)，我们需要将其分成在此函数之前发生的过程调用以及该调用后的所有过程。如果出站调用之后没有任何过程，并且出站调用到同一个函数，我们可以将其描述为“尾递归”，这可以使转换为迭代过程变得更加简单，只需将调用参数插入堆栈即可(Example)。实际上，将尾递归转换为迭代堆栈过程已帮助我在多个实例中克服了浏览器的递归深度限制。
转换为尾递归
为了将递归转换为尾递归，我们必须考虑如何处理从递归调用中传递的信息，以及是否可以转换此过程以利用递归本身中的参数。因为在您的特定示例中，调用结果唯一发生的是局部变量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)
(所有这些都是利用堆栈概念来排序我们的操作的技巧。如果您想获得真正的幻想(甚至更复杂)，请将每个指令编码为一个函数，并模拟具有暂停功能的实际call stack主程序中的下一条指令(将对其他功能的调用压入该指令)。)
现在，将这个想法应用到您的示例中:
同步例子
我们不仅在这里有调用后处理程序，而且在整个此类调用中都有一个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());调用堆栈仿真
我不确定是否有时间解决这个问题，但是这里有一些有关通用模板的想法。将其他函数调用为相关的较小函数的单独函数，以使执行暂停，也许将它们编码为具有一系列操作和键的对象，以模拟局部变量。
然后编写一个 Controller 和接口(interface)，该 Controller 和接口(interface)可以区分对另一个函数的调用(如果它也具有出站调用，则类似地编码)，将该“函数”的对象(或堆栈框架)插入堆栈，记住下一个的位置符合指令。使用对象键作为被调用函数的“返回地址”，例如，可以使 Controller 知道，可以使用JavaScript来完成许多创造性的方法。
正如其他人在这里指出的那样，每个调用另一个函数的函数都面临着将其转换为迭代序列的挑战。但是可能有许多功能可能适合这种方案，并使我们受益于对执行限制和排序的额外控制。
关于javascript - 如何将同步和异步递归函数转换为JavaScript中的迭代，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47949479/